숫자 변환하기

<숫자 변환하기>는 주어진 x, y, n의 값으로 연산하는 최적의 방법을 찾는 문제다. x를 y로 만들 수 있는 최소의 연산 횟수를 반환해야 하며, 사용할 수 있는 연산은 다음과 같다.

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

처음에는 또 홀린 듯이 재귀로 풀었다...

function solution(x, y, n) {
    const calc = (num) => {
        if (num === y) return 0;
        if (num > y) return -1;
        const ret = [calc(num + n), calc(num * 3), calc(num * 2)].filter((el) => el !== -1);
        return ret.length === 0 ? -1 : Math.min(...ret) + 1;
    }
    return calc(x);
}

테스트 케이스로 주어지는 문제는 모두 통과했지만 제출하면 런타임 에러가 줄줄 터졌다... 재귀를 너무 깊게 들어가서라고 판단하여 중복되는 값을 제외하는 코드를 추가했다.

그래도 안되더라!! 결국 dfs를 포기하고 bfs 방식으로 풀었다. 사실 생각해보면 연산 결과가 차례대로 축적되는 것이기 때문에 bfs를 떠올렸어야 하는게 맞는데, 습관적으로 dfs를 사용한 것 같다.

function solution(x, y, n) {
    const visited = {};
    const queue = [x];
    
    if (x === y) return 0;
    visited[x] = 0;
    while (queue.length) {
        const before = queue.shift();
        for (const after of [before + n, before * 2, before * 3]) {
            if (after > y || visited[after]) continue;
            if (after === y) return visited[before] + 1;
            visited[after] = visited[before] + 1;
            queue.push(after);
        }
    }
    return -1;
}

이렇게 큐를 사용한 bfs로 풀면 통과는 한다. 하지만 테스트 9, 10번에서 7000ms, 4000ms라는... 어마어마한 효율을 경험하게 된다. 아무래도 js에는 큐가 없기 때문에 shift() 함수를 사용함에 있어서 오는 문제라고 생각했다. 그래서 찾아보니 아래처럼 큐를 아예 새로 할당해주는 방법이 있더라.

function solution(x, y, n) {
    const visited = {};
    let queue = [x];
    
    if (x === y) return 0;
    visited[x] = 0;
    while (queue.length) {
        const newQueue = [];
        for (const before of queue) {
            for (const after of [before + n, before * 2, before * 3]) {
                if (after > y || visited[after]) continue;
                if (after === y) return visited[before] + 1;
                visited[after] = visited[before] + 1;
                newQueue.push(after);
            }
        }
        queue = newQueue;
    }
    return -1;
}

이렇게 newQueue를 새로 만들어 반복문을 돌 때마다 queue에 새로 할당해 주면 놀랍게도 7000ms나 걸리던 저 함수가 170ms대로 줄어든다.

레벨 2에 있는 문제를 풀면 풀수록 문제만 풀고 있을 게 아니라 정말로 이론 공부를 좀 해야겠다는 생각이 든다. 아마 조만간 공부할 거리를 찾아서 새로운 포스팅을 하지 않을까 싶다. 알고리즘 재미있다~~!~!!!