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

문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.
  자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

문제풀이

1. y 길이값만큼 배열을 생성하여 무한값을 넣어준다.
2. x와 y가 같으면 변경할 필요가 없기 때문에 0으로 리턴해준다.
3. 처음 값은 0으로 셋팅해준다.
4. y에서 x로 1씩 감소하면서
   4-1. i-n이 0보다 크면 해당 값에 작은 값을 넣어준다.
   4-2. i가 2로 나누어떨어지면 해당 위치의 값과 현재값에서 1을 더한 값중 작은 값을 넣어준다.
   4-3. i가 3으로 나누어떨어질 경우도 4-2로 동일.
5. x의 값이 무한이면 변경할 수 없기 때문에 -1을 반환하고 아니면 해당 값을 반환한다.

코드

function solution(x, y, n) {
    let arr = new Array(y+1).fill(Infinity);
    
    if(x==y) return 0;
    
    if(y-n>0) arr[y-n] = 1;
    if(y%2==0) arr[y/2] =  1;
    if(y%3==0) arr[y/3] = 1;
    
    for(let i=y-1; i>=x; i--){
        if(i-n>0) arr[i-n] = Math.min(arr[i-n], arr[i]+1);
        if(i%2==0) arr[i/2] =  Math.min(arr[i/2], arr[i]+1);
        if(i%3==0) arr[i/3] = Math.min(arr[i/3], arr[i]+1);
    }
    return arr[x] == Infinity ? -1 : arr[x];
}

리팩토링

function solution(x, y, n) {

    if(x==y) return 0;
    
    let arr = new Array(y+1).fill(Infinity);
    arr[y] = 0;
    
    for(let i=y; i>=x; i--){
        if(i-n>0) arr[i-n] = Math.min(arr[i-n], arr[i]+1);
        if(i%2==0) arr[i/2] =  Math.min(arr[i/2], arr[i]+1);
        if(i%3==0) arr[i/3] = Math.min(arr[i/3], arr[i]+1);
    }
    return arr[x] == Infinity ? -1 : arr[x];
}

다른 사람 코드

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