[Java] 프로그래머스 - 마법의 엘리베이터

https://school.programmers.co.kr/learn/courses/30/lessons/148653?language=java

프로그래머스

시나리오

현재 층수의 일의 자릿수를 조사, 5보다 크면 (10-일의 자릿수)만큼 덧셈하고, 작으면 일의 자릿수만큼 뺄셈하여 끝자리를 0으로 맞춘다. 한번에 이동할 수 있는 층수는 절댓값이 \(10^c)\인 정수이기 때문이다.

일의 자릿수를 덧셈/뺄셈하여 끝자리를 맞췄다면 다음으로 십의 자릿수를 조사, 같은 방법으로 해당 자릿수를 0으로 맞춘다. 이 과정은 가장 앞자리까지 반복하며, 덧셈/뺄셈한 값만큼 누적하여 return한다.

 

다만 각 자릿수가 5라면, 현재 자릿수의 앞자릿수를 조사한다. 이 때 앞자릿수가 5이상이면 덧셈하는 것이 유리하고, 5미만이라면 뺄셈하는 것이 유리하다.

 

 

이 시나리오는 정답 코드들의 시나리오를 가져온 것이며 

첫번째 시도는 무작정 BFS로 풀었다.

첫 시도

import java.util.*;

class Solution {
    public int solution(int storey) {
        int answer = 0;
        answer = bfs(storey);
        return answer;
    }

    //bfs. +_1 ~ +-100까지 적용한 모든 경우 enqueue 
    private int bfs(int s){
    //chk를 통해 이미 간 곳은 가지 않도록. chk배열을 int로 해서 특정 층까지 가는 데 소요된 마법의 돌 개수 카운팅
        boolean[] chk = new boolean[100000001];
        chk[s]=true;
        Queue<int[]> q = new LinkedList<>();

        int[] init = {s,0};
        q.offer(init);

        while(!q.isEmpty()){
            int[] polled = q.poll();
            System.out.println(Arrays.toString(polled));
            if(polled[0]==0){
                return polled[1];
            }
            //절댓값이 10^c인 수를 +/- 했을 때 조건 비교 및 enqueue
            for(int i=0; i<=8; i++){
                int res = polled[0]-(int)(Math.pow(10,i));
                if(res>=0 && !chk[res]){
                    chk[res]=true;
                    int[] e = {res, polled[1]+1};
                    q.offer(e);
                }
                res = polled[0]+(int)(Math.pow(10,i));
                if(res<=100000000 && !chk[res]){
                    chk[res]=true;
                    int[] e = {res, polled[1]+1};
                    q.offer(e);
                }
            }
        }
        return -1;
    }
}

//가지치기
/*
    ???
*/


//마법의 돌의 최소 값

각 자릿수를 비교하여 정답을 도출한게 아니라 1부터 1억까지 더하거나 빼는 모든 경우의 수를 BFS로 구했기 때문에 그 가짓수가 너무 많아졌고, 예시 테스트케이스는 통과했으나 대부분의 테스트케이스에서 시간초과가 발생하였다.

 

 

내가 풀 수 없음을 직감하고 정답 코드들을 참고했고 그들의 시나리오를 참고한 뒤 혼자 푼 코드이다.

 

두번째 시도

class Solution {
    private int answer=0;

    public int solution(int storey) {
        while(storey!=0){
            storey = calcStorey(storey);
        }
        return answer;
    }

    //자릿수 계산 하여 갱신된 층수 반환
    private int calcStorey(int storey){
        int div = storey%10;
        if(div<5){
            storey-=div;
            calcAnswer(div);
        }else if(div>5){
            storey+=10-div;
            calcAnswer(10-div);
        }else{
            if(hasToAdd(storey)){
                storey+=div;
            }else{
                storey-=div;
            }
            calcAnswer(div);
        }
        if(storey/10<=0){
            return 0;
        }
        return storey/10;
    }

    //answer누적합
    private void calcAnswer(int num){
        answer+=num;
    }

    //현재 자릿수가 5일 때 앞자리를 보고 판단하는 함수
    private boolean hasToAdd(int storey){
        if(storey<10){
            return false;
        }
        if(storey/10%10<5){
            return false;
        }
        return true;
    }
}

//자릿수가 5일 때는 앞자리 수를 보고 판단. 앞자리 수가 5이상이면 현재 자릿수를 더하고 5보다 작으면 현재 자릿수를 빼는 게 더 적은 층을 이동할 수 있다.

//입력받은 현재 층수에 대해 일의 자릿수를 조사, 5보다 크면 10-일의 자릿수 만큼 더하고, 작으면 뺄셈하여 10의 약수로 맞춘다. 현재 층수의 일의 자릿수부터 조사, 층수를 반올림하고 이동한 칸만큼 answer+=, 다음 자릿수를 조사하기 위해 storey//10. 반복


//TC
// +4: 20 -> +2 : 0
//4+2=6

// +4: 2550 -> +5: 2600 -> +4: 3000 -> +3: 0
// +4: 2550 -> +5 :2500 -> +5: 2000 -> +2: 0
//4+5+4+3 = 16

BFS로도 가지치기를 잘한다면 풀 수 있겠지만, 각 자릿수를 활용하는 아이디어를 활용했을 때 가장 효율적인 문제라고 생각한다.

문제를 풀다보면 이렇게 최단거리?를 구해야하는 경우가 종종 있는데 자릿수를 반올림하는 아이디어로도 풀 수 있음을 배울 수 있었다.