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

https://school.programmers.co.kr/learn/courses/30/lessons/148653

프로그래머스

 

1. 실패한 풀이 (BFS탐색) 시간초과

package Programmers;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class 마법의엘리베이터 {
    static int[] ch;
    static int[] floor ;
    static int minL = Integer.MAX_VALUE;
    static Queue<Integer> q = new LinkedList<>();
 
    public static void main(String[] args){
        int storey = 2554;
        마법의엘리베이터 T = new 마법의엘리베이터();
        T.solution(storey);
    }
 
    public int solution(int storey) {
        int answer = 0;
        // -1, 1, -10, 10, -100, 100
 
        List<Integer> tempFloor = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            int tempPow = (int)Math.pow(10, i);
            tempFloor.add(tempPow);
            tempFloor.add(-tempPow);
        }
        floor = new int[tempFloor.size()];
        for (int i = 0; i < tempFloor.size(); i++) {
            floor[i] = tempFloor.get(i);
        }
 
        ch = new int[100000001]; //층수의 크기만큼 저장
        ch[storey] = 1; //시작점 체크
        q.offer(storey); //시작점추가
        bfs(storey);
 
        answer = minL;
        return answer;
    }
 
    public void bfs(int s){
        int L = 0;
        //q 가 빌때까지 돈다
        while (!q.isEmpty()){
            //q 들어있는 크기만큼 사이즈의 for문을 돈다 bfs 단계를 알기위해서
            int qs = q.size();
            for (int i = 0; i < qs; i++) {
                int t = q.poll();
                if(t == 0){
                    minL = Math.min(minL, L);
                    return; //q가 0이면 반환한다.
                }
                //갈수있는 층수만큼 돈다.
                for (int j = 0; j < floor.length; j++) {
                    int nextFloor = t + floor[j];
                    if(nextFloor >=0 && nextFloor <= 100000000 && ch[nextFloor] == 0){
                    ch[nextFloor] = 1;
                    q.offer(nextFloor);
                    }
                }
            }
            L++; //bfs 한바퀴돌때마다 단계를 추가해준다.
        }
    }
}

실패

 

음 탐색범위가 너무 넓다. 

 

1. 수정한 코드 

package Programmers;
public class 마법의엘리베이터 {
    public static void main(String[] args){
        int storey = 2554;
        마법의엘리베이터 T = new 마법의엘리베이터();
        T.solution(storey);
    }
    public int solution(int storey) {
        int answer = 0;
        //storey가 0이 될때까지 돌린다.
        while (storey != 0){
            int cur = storey % 10;
            int next = (storey / 10) % 10;
            if(cur > 5){
                answer += 10 - cur; //6이면 4만큼 버튼을 누른거다.
                storey += 10;
            }else if(cur == 5){
                //앞자리가 4이하면 현재자리수의 5는 빼는게 이득 앞자리가 6이면 현재자리 5는 더하는게 이득
                answer += 5; //cur가 5면 더하거나 빼는건 카운팅이 똑같은데 next 숫자만 더해줄지 그냥 냅둘지 정하면됨
                if(next >= 5){
                    storey += 10; //next가 5보다 크면 10을 더해주면 현재 storey에서 next +1 이된다.
                }else{
                    storey += 0; //5보다 작으면 기냥 냅둔다.
                }
            }else{
                answer += cur;
            }
            storey /= 10; //1의 자리숫자는 계산된거니까 날려준다.
        }
        return answer;
    }
}

 

1. 10 의 배수만 버튼으로 주어지니까 단순 경우의수만 생각하고 1의 자리 숫자가 

5보다 큰지, 5인지 > (10의자리 숫자가 5보다 큰지 5보다 작은지), 5보다 작은지 

 

※ 알고리즘 공부하다보니 DFS BFS 중독인거같다 

최소거리나 경우의수 보면 DFS BFS 쓰고싶음 (쓰고나면 시간초과될까바 두렵)

(버튼의 종류가 임의의 숫자면 BFS를 썼어야겠지만 10의 배수이기때문에 쉽게 풀린다. )