[Greedy] 마법의 엘리베이터 (실패분석 - 시간초과)

접근

마법의 엘리베이터

사실 비슷한 문제를 백준에서 풀어보았습니다.
이 문제는 올림을 어떻게 처리할 것인가를 생각했다면 쉽게 풀었을거 같습니다.

하지만 저는 BFS로 접근하자고 생각했습니다.
문제에서 주어진 수가 1 ≤ storey ≤ 100,000,000이었기 때문에 시간 초과가 발생했습니다.
BFS는 모든 경우의 수를 생각하기 때문입니다.

따라서 문제를 다시 읽어보면 한가지 힌트가 있습니다.
바로 4일 경우에는 -1씩 4번 버튼을 누르는 것이 이득이지만
6일 경우에는 +1씩 4번 버튼을 눌러서 10으로 만들고 -10의 버튼을 누르는 것이 이득입니다.

아래와 같은 흐름으로 갑니다

storey = ⏺️⏺️⏺️⏺️
4자리의 수라고 가정할 때
엘리베이터와 같이 1의 자리 숫자부터 접근합니다.
현재 엘리베이터에서 빼야하는 자리의 층수 = storey%10;
남은 엘리베이터 층수= storey = storey/10;
storey가 0이 아닐때까지 반복

근데 문제를 풀다보니 몇 개의 테스트 케이스에서 실패라고 떠서 왜 뜨는지 원인을 찾아보았습니다.
3가지 경우로 생각해봐야 하는것을 깨달았습니다.

• 5보다 작은 경우
  현재 엘리베이터에서 빼야하는 자리의 층수를 연산 횟수에 더합니다.
• 5보다 큰 경우
  (10 - 현재 엘리베이터에서 빼야하는 자리의 층수)를 연산 횟수에 더합니다.
  남은 엘리베이터 층수 = 남은 엘리베이터 층수 +1
• 5인 경우
  이 부분이 중요합니다.
  남은 엘리베이터 층수의 1의 자리가 5보다 작은지 5보다 같거나 큰지에 따라 연산의 방법이 달라집니다.
  • 5보다 작은 경우
    현재 엘리베이터에서 빼야하는 자리의 층수를 연산 횟수에 더합니다.
  • 5보다 큰 경우
    (10 - 현재 엘리베이터에서 빼야하는 자리의 층수)를 연산 횟수에 더합니다.
    남은 엘리베이터 층수 = 남은 엘리베이터 층수 +1

위의 조건을 모두 만족하도록 풀이를 구현했습니다.

시간초과가 발생한 풀이와 올림 방식을 활용한 두 개의 풀이를 다음과 같이 정리합니다.

시간 초과가 발생한 풀이 (BFS)

import java.util.*;

class Solution {
    
    static  int result =Integer.MAX_VALUE;
    static int max=0;
    
    public int solution(int storey) {
        int answer = 0;
        // 절대값이 10의 c승 
        // 더한 결과가 0보다 작은 경우에는 움직이지 않는다.
        // 버튼 1번당 마법의 돌 한개
        // 마법의 돌을 적게 사용하는 방법
        
        //BFS인데 어떻게 저 많은 수를 고르냐에 문제
        //1. storey의 자릿수를 구한다.
        //2. 그 자리의 반복은 0부터 시작하여 list에 넣고
        //3. 그 값에 따라 BFS 진행
        
        //1번 과정
        int length = Integer.toString(storey).length();
        //2번 과정
        ArrayList<Integer> list = new ArrayList<>();
        
        // 엘리베이터에서 누를 수 있는 모든 버튼
        for(int i=0;i<=length;i++){
            int input = (int)(Math.pow(10,i));
            list.add(input);
            list.add(-1*input);
        }
        
        //단위
        int t = (int)(Math.pow(10,length-1));
        
        // 앞 자리
        int index = storey%t==0? storey/t: storey/t +1;
        
        max= index*t;
           
        //0부터 20까지
        boolean[] visited = new boolean[max+1];
        System.out.println(index*t);
        
        
         bfs(storey,list,visited);
        
        return result;
    }
    
    // 엘리베이터 버튼을 활용하여 0을 만들 수 있는 모든 경우의 수
    static void bfs(int storey, ArrayList<Integer> list, boolean[] visited){
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{storey,0});
        visited[storey]=true;
        
        while(!q.isEmpty()){
            
            int[] output = q.poll();
            
            if(output[0]==0){
                if(result>output[1])
                    result = output[1];
            }
            
            for(int l : list){
             
             if( output[0]+l>=0 && output[0]+l<=max && !visited[output[0]+l]){
                    visited[output[0]+l]=true;
                    q.offer(new int[]{output[0]+l,output[1]+1}); 
                }
                    
                    
        }        
            
        }
                      
    } 
    
}

정답 코드

import java.util.*;

class Solution {
    
    public int solution(int storey) {
        int answer = 0;
        
        while(storey!=0){
            // 마지막 숫자
            int at = storey%10;
            // 그 다음 남은 수
            storey=storey/10;
            // 마지막 숫자가 5보다 크거나 같은 경우
            if(at>5) {
                // 연산의 횟수에 더하기
                answer+=10-at;
                // 앞자리 수 바뀌기
                 storey+=1;
            }else if(at<5){
                // 연산의 횟수에 더하기
                answer+=at;
            // at가 5인 경우
            }else{
                if(storey%10>=5){
                    answer+=10-at;
                    storey+=1;
                }else{
                    answer+=at;
                }
            }
        }
        return answer;
    }
    
}