프로그래머스 - Level 2. 숫자 변환하기 / JavaScript (js)

문제설명

문제분석

이 문제는 x에서 출발하여 y까지 도달하는 여정을 BFS 형태로 접근해서 해결하면 됩니다. memoization을 이용해 접근하면 반복된 연산을 줄일 수 있습니다.

이해하기 쉽게 코드작성하기

function solution(x, y, n) {
    let answer = Infinity;
    // 최초 방문하는 num과 그 depth
    const queue = [{ num: x, depth: 0 }];
    const visitedNum = { [x]: true };
    
    do {
        const { num, depth } = queue.shift();
        
        if(num === y) return depth;
        
        const nextNums = [num + n, num * 2, num * 3];
        // 각 연산에 대해
        for(const nextNum of nextNums) {
            // 결과와 같은지 검사
            if(nextNum === y) {
                answer = Math.min(answer, depth + 1);
                continue;
            }
            // 결과와 다르고, 방문한 적이 없다면 업데이트
            if(num <= y && visitedNum[nextNum] === undefined) {
                queue.push({ num: nextNum, depth: depth + 1 });
                visitedNum[nextNum] = true;
            }
        }
    } while(queue.length > 0)
    
    return answer === Infinity ? -1 : answer;
}

요즘 문제 좀 풀었다고, 금방 코드가 깔끔하게 쑥쑥 써져서 좀 뿌듯했습니다. 그러나.... 어김없이 만나버린 그 빨간 글씨...

대체 어떻게 해야 시간을 줄일수 있을지 고민해보겠습니다. 일단 DP를 이용한 접근으로 변환해보겠습니다.

 

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

0부터 y까지, 각 요소가 Infinity로 초기화된 배열 dp를 선언합니다. dp[i]는 i를 만드는 데에 필요한 최소 연산 횟수를 저장할 겁니다. dp[x]를 만드는 최소 연산 횟수는 0이므로 dp[x]를 0으로 초기화합니다.

 

for문을 돌면서 dp 배열을 채웁니다. (i - n)이 x보다 크거나 같은 경우, i를 2나 3으로 나눌 수 있는 경우에 dp를 업데이트 합니다.

 

마지막으로 dp[y]를 리턴합니다. 이때 dp[y]가 Infinity라면 업데이트되지 않은 요소라는 뜻이므로 x를 y로 변환할 수 없다는 말과 동일하기 때문에 -1을 리턴합니다.

 

시간을 줄이려고 dp를 이용한 접근으로 변경했는데, 코드도 훨씬 간결한 게 보기가 좋습니다. 앞으로는 dp를 좀 더 적극적으로 사용해보겠습니다.