[DP] 프로그래머스 '숫자 변환하기' - js

1. 문제

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

프로그래머스

2. 코드

처음 작성한 코드) 일부 타임 아웃

큐를 이용하지 않아서 타임아웃이 뜬건가 싶기도 하다ㅠㅠ 근데 큐를 이용하는 방법을 모르겠는걸

function solution(x, y, n) {
    let answer = -1;
    
    const bfs = (newY, total) => {
        if(newY === x) {
            if(answer !== -1) answer = answer > total ? total : answer;
            else answer = total;
        }
        else if(x < newY){
            if(newY - n >= x) bfs(newY - n,total+1);
            if(newY / 2 >= x) bfs(newY / 2,total+1);
            if(newY / 3 >= x) bfs(newY / 3,total+1);
            else answer === -1;
        }
    }
    
    bfs(y,0);

    return answer;
}

정답 코드)

역시나 예상은 했지만 dp로 풀었어야 했다. dp가 왜 익숙해지지 않는걸까^^

기억하자..dp는 이전 값 저장에 포커스를 둔다...

function solution(x, y, n) {
  if (x === y) return 0;
  const dp = {};
  dp[x] = 0; // 수들이 더하거나 곱해져 갈 때 바뀐 횟수 count하기 위해 이전 값에 횟수 저장해놓고 사용
  let data = [x]; // 조건에 맞게 더하거나 곱해준 수
  while (data.length) {
    const newData = [];
    for (const d of data) {
      for (const e of [d + n, d * 2, d * 3]) {
        // 새로운 수가 y보다 크거나
        // 새로운 수가 이미 이전 순서에서 나왔을 때
        if (e > y || dp[e]) continue;
        // 새로운 수가 y와 같을 때 이전 숫자에 저장된 횟수 + 1 리턴
        if (e === y) return dp[d] + 1;
        // 새로운 수가 위 어느 조건에도 성립하지 않으면 이전 숫자에 저장된 횟수 + 1을 새로운 수의 값으로 저장
        dp[e] = dp[d] + 1;
        newData.push(e); // 비교 대상 리스트에 새로운 수 추가
      }
    }
    data = newData; // 비교 대상 숫자 리스트 바꿔주기
  }
  
  return -1;
}

 

복기

6/14