[JS] 숫자 변환하기

문제

처음 풀이 (오답 -> 시간 초과)

function solution(x, y, n) {
    var answer = 0;
    const queue = [[x, 0]];
    
    if (x === y) {
        return 0;
    };
    
    while (queue.length !== 0) {
        const [num, count] = queue.shift();
        if (num * 2 === y || num * 3 === y || num + n === y) {
            answer = count + 1;
            break;
        };
        
        if (num < y) {
            queue.push([num + n, count + 1]);
            queue.push([num * 2, count + 1]);
            queue.push([num * 3, count + 1]);
        };
    };
    
    return answer === 0 ? -1 : answer;
}

큐 방식을 통해 BFS로 풀었습니다. 하지만 시간초과.. JS의 shift()는 O(n)만큼의 시간 복잡도를 갖고 있기 때문에 시간 제한내에 풀기 어려웠습니다. 그래서 dp 방법을 통한 메모이제이션으로 불필요한 연산을 막아서 풀었습니다.

정답 풀이

function solution(x, y, n) {
    var answer = 0;
    
    if (x === y) return 0;
    const dp = {};
    let data = [x];
    dp[x] = 0;
    
    while (data.length) {
        const newData = [];
        for (const d of data) {
            for (const e of [d*2, d*3, d+n]) {
                if (e > y || dp[e]) continue;
                if (e === y) {
                    return dp[d] + 1;
                };
                newData.push(e);
                dp[e] = dp[d] + 1;
            }
        };
        data = newData;
    };
    return -1;
}

dp를 사용했고 for문을 이용한 풀이입니다.
dp에는 연산 횟수를 저장했고 data 배열은 연산해야하는 값들이 저장되어 있습니다.

문제 해결 아이디어입니다.

• 만약 x 와 y 가 같다면 0 리턴
• data 배열 안의 값들을 순회하면서 각 연산을 수행한다. [d2, d3, d+n]
• 각 연산 값이 y보다 크거나 이전에 수행했던 연산일 경우 continue
• 각 연산이 정답이라면 dp[d]에 +1을 해주고 return
• newData에 각 연산 값을 push, dp에 새로운 연산 횟수 저장
• 배열 data를 newData로 교체
• 모든 연산이 끝났는데도 return이 되지 않았다면 -1 리턴