숫자 변환하기

 

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> mem=new HashSet<>();
        int idx=0;
        que.add(x);
        if(x==y){
            return 0;
        }
        while(!que.isEmpty()){
            idx+=1;
            int queidx=que.size();
            for(int i=0; i<queidx; i++){
                int num=que.poll();
                if((num+n)==y || ((num*2)==y) || ((num*3) == y)){
                    return idx;
                }
                if((num+n)<y && !mem.contains(num+n)){
                    que.add(num+n);
                    mem.add(num+n);
                }
                if((num*2)<y && !mem.contains(num*2)){
                    que.add(num*2);
                    mem.add(num*2);
                }
                if((num*3)<y && !mem.contains(num*3)){
                    que.add(num*3);
                    mem.add(num*3);
                }
            }
        }
        return -1;
    }
}

 

단순히 que에 집어넣기만 하면 규모가 큰 일부 연산에서는 시간초과가 발생한다.

필요한 값은 최소 연산 횟수이기 때문에, 이미 나왔던 값이라면 반복할 필요가 없으므로 메모이제이션으로 연산 횟수를 최적화하여 해결할 수 있다.