문제

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

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

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

입출력

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

예시 설명

• 입출력 예 #1
  x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

• 입출력 예 #2
  x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

• 입출력 예 #3
  x를 y로 변환할 수 없기 때문에 -1을 return합니다.

코드 풀이

• 큐를 통해서 2,3곱한 수, n을 더한 수 모든 경우를 큐에 담고, 각 원소에 몇번 연산이 되는지 카운트를 한다.
• queue 내부에서 연산한 값이 y와 같을 경우 반복문을 멈춘다.
• queue가 비어있거나, 연산값이 x보다 작을 경우도 마찬가지로 반복문을 멈추고 -1를 출력한다.

function solution(x, y, n) {
  let answer = -1;
  const queue = [{ num: y, count: 0 }];
  while (queue.length !== 0) {
    const { num, count } = queue.shift();

    if (num === x) {
      answer = count;
      break;
    }

    if (num % 2 === 0) {
      queue.push({ num: num / 2, count: count + 1 });
    }
    if (num % 3 === 0) {
      queue.push({ num: num / 3, count: count + 1 });
    }
    if (num - n >= x) {
      queue.push({ num: num - n, count: count + 1 });
    }
  }
  return answer;
}

후기

첫 문제의 코드를 풀이 할 때, 반복문을 통해서 연산할 때 마다, y의 값과 연산한 값의 차이가 가장 적은 경우의 연산을 채택하는 코드를 작성하였다. 차이가 적지만 결과 값이 제대로 연산이 되지 않는 경우가 배제하여 다른 분들의 코드를 참고하고 문제 풀이를 하면서 느낀 점은 알고리즘이 어떤 것이 있고, 예제들을 풀어 보았지만, 매번 어떤 알고리즘을 어떻게 응용할지에 대해서 조금 더 고민을 많이 해야될 거 같다는 생각이 들었다.