[programmers] 숫자 변환하기

📝 [Lv2] 숫자 변환하기

👀 문제 설명

자연수 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

 

💻 입출력 예

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

 

✨ 풀이 설명

전형적인 BFS 문제로, 최소 횟수를 구할 때 많이 사용하는 방법이다. 각 단계의 값을 queue에 넣고, 해당 값들을 순차적으로 빼내어 연산을 한 후, 다시 queue에 넣는 작업을 반복한다.

checked 배열을 만들어 이미 지나갔던 값은 다시 방문하지 않도록 해준다. 가장 처음 방문했을 때의 연산이 최솟값이기 때문이다.

만약 모든 연산 결과에 해당하는 값이 없을 경우에는 -1을 반환해 주었다.

 

🕵️‍♂️ 코드

function solution(x, y, n) {

  const checked = new Array(y + 1).fill(0);

  checked[x] = 1;

  let queue = [x], cnt = 0;

  while (queue.length) {

    const tmp = queue.slice();

    queue = [];

    for (const exec of tmp) {

      if (exec === y) return cnt;

      for (const val of [exec + n, exec * 2, exec * 3]) {

        if (val <= y && !checked[val]) {

          checked[val] = 1;

          queue.push(val);

        }

      }

    }

    cnt++;

  }

  return -1;

}