[JS로 코테 준비하기] 17. 숫자 변환하기

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

프로그래머스

 

처음 봤을 때는 간단해 보였는데, 시간 초과를 해결하는 데 꽤 많은 시간이 걸렸다.

다양한 풀이가 가능해서 기록해 두려고 한다!

 

1. 재귀 (시간 초과)

• 가장 먼저 떠올렸던 풀이로, 문제를 그대로 코드로 옮겼다고 볼 수 있다.
• x에서 y를 만드는 모든 과정을 처리하고, x를 y로 변환하는 순간 result값을 업데이트한다.

function solution(x, y, n) {
    let result = Infinity;
    
    const go = (cur, step) => {
        if(cur === y){
            result = Math.min(result, step);
            return;
        }
        
        if(cur > y) return;
        
        go(cur + n, step + 1);
        go(cur * 2, step + 1);
        go(cur * 3, step + 1);
    }
    
    go(x, 0);
    
    return result === Infinity ? -1 : result;
}

 

 

2. BFS (shift 시간 초과)

• 최소 연산 횟수를 구하는 것이기 때문에 재귀 코드처럼 모든 방법을 구할 필요가 없다. (DFS(재귀)와 BFS의 차이를 확인할 수 있음)
• BFS를 활용해 가장 먼저 변환되는 것을 정답으로 처리하고 while문을 탈출한다.
• 그리고 y -> x 방향으로 변환하면 가지치기가 되면서 불필요한 함수 호출이 제거된다.
• 다만, 자바스크립트에서의 queue를 사용하기 위한 shift 메서드의 속도가 느리기 때문에 이 코드 또한 시간 초과가 발생한다. (직접 queue를 구현하면 통과할 수 있다)

function solution(x, y, n) {
    let result = -1;
    const q = [];
    q.push([y, 0]);
    
    while(q.length !== 0){
        const [value, step] = q.shift();
        if(value <= x) {
            if(value === x) result = step;
            break;
        }
        
        if(value - n >= x) q.push([value - n, step + 1]);
        if(value % 2 === 0 && value / 2 >= x) q.push([value / 2, step + 1]);
        if(value % 3 === 0 && value / 3 >= x) q.push([value / 3, step + 1]);
    }
 
    return result;
}

 

 

3. DP (성공)

• 드디어 통과.. DP를 활용하면 O(y - x)의 수행 시간을 확보할 수 있다.
• 메모이제이션을 위한 d[i]는 x에서 i를 만들 수 있는 최소 연산 횟수이다.
• x부터 y까지 돌면서 d[i]를 업데이트하는데, 가지치기를 위해 y -> x로의 변환하는 것처럼 처리한다.

function solution(x, y, n) {
    let d = [...Array(y + 1).fill(Infinity)];
    d[x] = 0;
    
    for(let i = x; i <= y; i++){
        if(i - n >= x) d[i] = Math.min(d[i], d[i - n] + 1);
        if(i % 2 === 0 && i / 2 >= x) d[i] = Math.min(d[i], d[i / 2] + 1);
        if(i % 3 === 0 && i / 3 >= x) d[i] = Math.min(d[i], d[i / 3] + 1);
    }
    
    return d[y] === Infinity ? -1 : d[y];
}