[프로그래머스] 숫자 변환하기 문제풀이 JS

처음엔 BFS로 접근하여 문제를 풀었는데,

 다른 사람의 풀이를 보니 DP가 훨씬 간결하여 DP로 다시 풀었다.

 

우선 x와 y는 같은 값일 수 있으니,

같은 값일 경우엔 변환이 필요없어서 0을 return한다.

 

여기서 dp객체는 key에 해당하는 숫자에 몇번의 변환을 거쳐서 도달했는지이다.

dp객체는 방문여부 판별에도 사용되서, 해당숫자에 가장 적은 변환으로 도달한 횟수가 저장된다.(if(!dp[value]))

dataList에는 숫자 변환이 필요한 숫자의 list가 저장되고,

dataList의 data들을 확인해서 n을 더했을때, 2를 곱했을 때, 3을 곱했을때 값들이

방문되었는지 확인하고, 해당 값이 y보다 작을 때는 다시 변환이 필요하므로

newDataList에 업데이트하고,

y일때는 그때까지 변환횟수에 1을 더한 결과를 return한다.

해당 과정을 마치고 dataList는 newDataList로 변경 후 다시 위 과정을 y가 나오거나 dataList가 빌 때까지 반복한다.

 

모든 과정을 끝냈는데 return값이 없다면 x가 y로 변환되지 못한 것이므로 -1을 return한다.

function solution(x, y, n) {
  if (x === y) return 0
  const dp = {}
  dp[x] = 0
  let dataList = [x]
  while (dataList.length !== 0) {
    const newDataList = []
    for (const data of dataList) {
      for (const value of [data + n, data * 2, data * 3]) {
        if (!dp[value]) {
          if (value === y) return dp[data] + 1
          else if (value < y) {
            dp[value] = dp[data] + 1
            newDataList.push(value)
          }
        }
      }
    }
    dataList = newDataList
  }
  return -1
}

 

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스