프로그래머스 코딩테스트 연습 - 숫자 변환하기 JavaScript

처음에는 DFS 방법으로 문제에 접근하였다.

function solution(x, y, n) {
    let minTry = 1000000;
    const dfs = (num, tryCount) => {
        if(num > y) {
            return;
        } else if(num === y) {
            if(minTry > tryCount) {
                minTry = tryCount;
            }
            return;
        }
        dfs(num + n, tryCount + 1);
        dfs(num * 2, tryCount + 1);
        dfs(num * 3, tryCount + 1);
    }
    dfs(x, 0);
    return minTry === 1000000 ? -1 : minTry;
}

하지만, 시간초과 문제가 발생하였다.

문제를 다시 생각해보니, 최단거리를 찾는 것과 유사하다는 생각이 들어 BFS방법으로 문제에 접근하기로 하였다.

function solution(x, y, n) {
    const memo = {[x]: 0};
    let possibleNums = [x];
    if(x === y) return 0;
    
    while(possibleNums.length) {
        const tmp = [];
        for(let el of possibleNums) {
            for(let item of [el + n, el * 2, el * 3]) {
                if(item === y) {
                    return memo[el] + 1;
                }
                if(item < y && !memo[item]) {
                    memo[item] = memo[el] + 1;
                    tmp.push(item);
                }
            }
            possibleNums = tmp;
        }
    }
    
    return memo[y] ? memo[y] : -1;
}

하지만 중간에 단순 BFS로 하면 여전히 문제가 발생할까 우려가 되어 dynamic programming을 적용하기로 하였다.

dp는 아직 공부가 부족하기에, 여기저기서 배워온 것을 바탕으로 겨우 구현할 수 있었다.

다른 사람의 풀이를 보니, DFS로 구현한 사람도 있었는데 처음에 내가 생각했던 것에서 좀 더 고민해 봤으면 또 다른 해결 방법을 배울 수 있지 않았을까 하는 생각이 들었다.

하나의 문제에서 여러개의 해결법을 도출해낼 수 있도록 더 많은 공부가 필요함을 느낀다.