[프로그래머스] LEVEL2 숫자 변환하기 JAVA

숫자 변환하기

문제링크

풀이

dp
1. cnt에 각 숫자를 만들기 위한 횟수를 저장한다. (dp)
2. queue를 활용해 횟수별로 숫자를 꺼내서 y보다 같거나 작은 숫자가 만들어진다면 다시 큐에 담는다.
3. queue에서 꺼낸 숫자가 y면 끝낸다.
4. 만들수 있는 모든 숫자를 만들었지만 만들 수 없다면 -1을 리턴한다.

코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        
        int[] cnt = new int[1_000_001];
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(x);
        
        while(!queue.isEmpty()) {
            int size = queue.size();

            while( --size >= 0) {
                int cur = queue.poll();
                if (cur == y) {
                    return cnt[y];
                }
                
                int[] temp = new int[3];
                temp[0] = cur + n;
                temp[1] = cur * 2;
                temp[2] = cur * 3;
            
                for (int t : temp) {
                    if (t <= y && cnt[t] == 0) {
                        queue.offer(t);
                        cnt[t] = cnt[cur] + 1;
                    }
                }
                
            }
        }
        return answer;
    }
}