[JS] 숫자 변환하기 (+DFS, BFS, DP)

프로그래머스

문제 이해

처음 문제를 보자마자 재귀함수를 써야겠다고 생각했다. 아니면 JS의 재귀함수 횟수를 고려해서 배열을 써야겠다고 생각했다. 그래서 DFS와 BFS를 각각 재귀함수와 배열로 구현했는데, 시간이 초과되어 검색해볼 수 밖에 없었고 DP를 써야한다는 것을 알게 되었다.

 

방법 1 - DFS

먼저 가장 먼저 시도한 깊이 우선 탐색(DFS) 코드는 다음과 같다. 가장 값이 크게 변할 것 같은 연산부터 진행했다.

function solution0(x, y, n) {
  let answer = null;

  const DFS = (xx, lv) => {
    if (xx < y) {
      DFS(xx * 3, lv + 1);
      DFS(xx * 2, lv + 1);
      DFS(xx + n, lv + 1);
    } else if (xx === y) {
      answer = Math.min(answer??1000000, lv);
      return;
    } else {
      return;
    }
  };

  DFS(x, 0);

  return answer ?? -1;
}

 

하지만 역시 정답은 잘 나오지만 런타임 에러가 발생해 배열로 코드를 수정해야 했다.

 

방법 2 - BFS

사실 이 코드는 DFS를 배열로 구현하려는 것이 처음 의도였는데, 구현하고 보니 배열을 하나만 사용한 너비 우선 탐색(BFS)임을 나중에 알았다.

function solution(x, y, n) {
  let answer = null;

  const toVisit = [x];
  while (toVisit.length > 0) {
    const X = toVisit.shift();
    if(X === y) {
      answer = Math.min(answer??1000000, lv);
    }

    if (X*3 <= y) {
      toVisit.push(X*3)
    }
    if (X*2 <= y) {
      toVisit.push(X*2)
    }
    if (X+n <= y) {
      toVisit.push(X+n)
    }
  }

  return answer ?? -1;
}

 

이 코드 또한 시간초과가 떠서 찾아보니 `shift` 메소드의 시간복잡도가 `O(n)`이라는 것을 알게 되었다. 맨 앞 원소를 제거하고 뒤 원소들을 모두 한칸씩 앞으로 당겨오는 메소드이다보니 시간복잡도가 `O(n)`이라고 한다. 그래서 `splice`도 사용해봤는데, 마찬가지로 시간복잡도가 `O(n)`정도로 크다고 한다. (조금 더 정확히하자면 자르고 남은 부분의 개수에 따라 달라진다고 한다)

 

그래서 `shift`와 `splice` 메소드를 사용하지 않고 오로지 인덱스만을 사용해서 코드를 작성해보았다.

function solution(x, y, n) {
  let answer = null;

  const toVisit = [[0,x]];
  let idx = 0;
  while (toVisit[idx]) {
    const [lv, X] = toVisit[idx];
    if(X === y) {
      answer = Math.min(answer??1000000, lv);
    }

    if (X*3 <= y) {
      toVisit.push([lv+1, X*3])
    }
    if (X*2 <= y) {
      toVisit.push([lv+1, X*2])
    }
    if (X+n <= y) {
      toVisit.push([lv+1, X+n])
    }
    idx++
    if(idx > 500) {
      toVisit.splice(idx)
      idx = 0;
    }
  }

  return answer ?? -1;
}

 

하지만 이번엔 배열의 크기가 너무 커서 `실패 (signal: aborted (core dumped))` 오류를 마주했다. 그래서 위에 제시한 것처럼 `splice` 메소드로 중간중간 배열을 잘라주었지만 시간 초과를 벗어날 수 없었다.

 

방법 3 - DP

DP는 Dynamic Programming(동적 프로그래밍, 동적 계획법)의 약자로, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 즉 각종 정렬 알고리즘, 탐색 알고리즘 등을 설계하는 방법 중에 하나이다.

 

따라서 DP를 사용한 방법은 `x*3, x*2, x+n` 값을 정하는 것이 아니라 방법 1, 2에서 사용한 `lv`을 계산된 값의 위치에 저장할 것이다.

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

 

시간은 생각보다 오래걸리지만, `y`가 커지거나 `x`,`n`이 작은 경우에 따른 재귀 함수 횟수나 저장하는 배열이 커지는 문제를 해결할 수 있다. (위 코드는 출처에서 가져왔다.)

 

동적 프로그래밍에 대한 좀더 자세한 내용은 이 블로그에서 살펴볼 수 있다. 코드 예시는 파이썬으로 되어있지만 얼추 이해할 수 있을 것이다.