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

문제 설명 

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

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

제한사항
1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y
입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명
입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

 

첫 번째 풀이( 시간초과 ) 

function solution(x, y, n) {
    var answer =-1;
    
    let queue = [[x,0]];
    let visited = Array(y).fill(false);
    visited[x] = true;
    while(queue.length){
        let [now , count] = queue.shift();
        
        if(now === y) {
            answer = count;
            return answer;
        }
        
        
        if(!visited[now * 3] && now * 3 <= y){
            visited[now * 3] = true;
            queue.push([now * 3, count+1])
        }
        if(!visited[now * 2] && now * 2 <= y){
             visited[now * 2] = true;
            queue.push([now * 2, count+1])
        }
        if(!visited[now + n] && now + n <= y){
             visited[now + n] = true;
            queue.push([now + n, count+1])
        }
        
    }
    
    
    
    
    return answer;
}

 

처음 문제를 보고 bfs로 풀어야겠다고 생각해 x 를 queue에 처음 삽입하고 문제를 풀었는데 5,6번에서 시간초과가 났다.. 배열의 shift() 메서드 때문인 것 같아서 직접 queue를 선언해서 shift() 과정을 O(1) 로 줄일 수 있는 방법을 고민하고 있었다... 하지만 좀 더 간결히 할 수 있는 방법이 있을 것 같아서 계속 고민하다가 y를 시작으로 역방향으로 하면 어떨까 ? 하는 생각이 들었다.  

( ++ 그리고 문제를 보면 수가 줄어드는 경우는 없고 곱하거나 더하는 경우만 있기 때문에 굳이 visited배열이 필요하지 않을 것 같은데 선언한 점이 잘못됐다.. 

최종 풀이( 통과 )

function solution(x, y, n) {
    var answer = -1;
    
    let queue = [[y,0]];
 
    while(queue.length){
        let [now , count] = queue.shift();
        
        if(now === x) {
            answer = count;
            return answer;
        }
        
        if(now % 3 === 0 && y/3 >=x) queue.push([now/3 , count + 1]);
        
        if(now % 2 === 0 && y/2 >=x) queue.push([now/2 , count + 1]);
        
        if(now - n >= x) queue.push([now-n , count+1]);
        
    }
    return answer;
}

 

무작정 x 에서부터 y 꺄지 3가지 계산방식을 적용하는 것 보다 y에서 x 로 가는 방법이 경우의 수가 줄어드는 것을 볼 수 있다. 
예를들어 x가 10이고 y 가 40일 때 첫번째 연산만 생각해볼때 x -> y 로 시작한다면 x * 2 , x *3 , x+ n 을 하고 y가 나올때까지 queue에 삽입 해야하지만  y -> x 로 시작한다면 40 % 3 은 되지 않으므로 40 % 2 와 40 - n 의 수만 삽입 하면 된다. 

오늘도 새로운 지식을 습득해 뿌듯하다 .. !