[프로그래머스] 숫자 변환하기 (JS)

풀이 과정

DP
1. 현재 연산 결과를 키, 연산 횟수(최솟값)를 값으로 하는 dp 객체 생성
2. 최적의 값을 큐에 넣고 BFS 방식으로 순회
3. n을 더한 값, 2를 곱한 값, 3을 곱한 값에 대해 반복
4. 현재 값이 y보다 커졌거나 이미 dp에 등록된 값이 있으면 넘어가기
현재 값이 y면 결과 리턴
아니면 dp 객체와 큐에 현재 결과를 추가
5. 모든 과정을 했는데도 리턴이 안 됐다면 -1 리턴

코드

function solution(x, y, n) {
  if (x === y) return 0;
  const dp = {};
  dp[x] = 0;
  let q = [x];
  while (q.length) {
    const tmp = [];
    for (const curr of q) {
      for (const next of [curr + n, curr * 2, curr * 3]) {
        if (next > y || dp[next]) continue;
        if (next === y) return dp[curr] + 1;
        dp[next] = dp[curr] + 1;
        q.push(next);
      }
    }
    q = tmp;
  }
  return -1;
}

🦾

처음에 혼자 힘으로 재귀로 풀고서 좋아했는데 몇몇 테스트 케이스에서 시간 초과가 났다.
결국 사람들의 힌트를 참고해서 DP 방식으로 다시 풀었다.
DP => 메모이제이션해서 연산 횟수 줄이기
또 BFS 방식에서 보통 shift()를 쓰는데, 이렇게 해도 풀리긴 하지만 큐의 길이가 길어지면 엄청나게 느려져서 오히려 반복문을 사용하는 것이 더 빠르다는 것도 알게 됐다.