[프로그래머스] 숫자 변환하기 (자바)

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

프로그래머스

 

문제

주어진 X 를 X * 2 or X * 3 or X + n 3가지 연산을 선택하여 Y 로 만들 수 있을 때

최소한의 연산횟수를 구하는 문제 

 

---

풀이

최소한의 횟수를 구하기 위해 BFS 를 사용했다. 

단 연산을 하면서 중복되는 숫자값이 나올 수 있기에 흔히 visited 처럼 숫자를 걸러주어야 시간초과가 발생하지 않는다. 

 

[0] 번 인덱스에는 숫자 결과값을 넣고

[1] 번 인덱스에는 연산 횟수를 넣어주었다. 

 

 

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<int[]> queue = new LinkedList<>();
        
        if (x == y)
            return 0;
        
        queue.add(new int[]{x * 2, 1});
        queue.add(new int[]{x * 3, 1});
        queue.add(new int[]{x + n, 1});
        Set<Integer> set = new HashSet<>();
        set.add(x * 2);
        set.add(x * 3);
        set.add(x + n);
        
        while(!queue.isEmpty()) {
            int[] tmp = queue.poll();
            
            if (tmp[0] == y)
                return tmp[1];
            
            if (tmp[0] * 2 <= y && !set.contains(tmp[0] * 2)) {
                queue.add(new int[]{tmp[0] * 2, tmp[1] + 1});
                set.add(tmp[0] * 2);
            }
    
            if (tmp[0] * 3 <= y && !set.contains(tmp[0] * 3)) {
                queue.add(new int[]{tmp[0] * 3, tmp[1] + 1});
                set.add(tmp[0] * 3);
            }
    
            if (tmp[0] + n <= y && !set.contains(tmp[0] + n)) {
                queue.add(new int[]{tmp[0] + n, tmp[1] + 1});
                set.add(tmp[0] + n);
            }
        }
        
        
        return -1;
    }
}