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

문제 설명

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

• x에 n을 더하기
• x에 2를 곱하기
• x에 3을 곱하기

최소한의 연산으로 x를 y로 만들 수 있는 횟수를 구해야 하며, 변환이 불가능한 경우 -1을 반환해야 합니다.

---

제한 사항

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

---

해결 방법

알고리즘: BFS (너비 우선 탐색)

• BFS를 사용하여 x에서 y로 변환하는 최소 연산 횟수를 찾습니다.
• 큐를 이용해 가능한 연산 결과를 탐색하며, 방문한 숫자를 기록하여 중복 탐색을 방지합니다.
• 목표값 y를 찾으면 해당 연산 횟수를 반환하고, 모든 경우를 탐색한 후에도 찾지 못하면 -1을 반환합니다.

---

시간 복잡도

• BFS는 한 노드를 한 번씩 탐색하므로 O(N)의 시간 복잡도를 가집니다.
• 최악의 경우 y까지 모든 수를 확인해야 하므로 O(y-x)가 될 수 있습니다.

---

구현 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(value) {
    const node = new Node(value);

    if (this.size === 0) {
      this.front = node;
    } else {
      this.rear.next = node;
    }

    this.rear = node;
    ++this.size;
  }

  dequeue() {
    if (this.size === 0) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;
    --this.size;

    if (this.size === 0) {
      this.rear = null;
    }

    return value;
  }
}

function solution(x, y, n) {
  let q = new Queue();
  let visit = new Set();
  let count = 0;

  q.enqueue(x);
  visit.add(x);

  if (x === y) return 0;

  while (q.size > 0) {
    let size = q.size;
    for (let i = 0; i < size; ++i) {
      const num = q.dequeue();

      for (const next of [num + n, num * 2, num * 3]) {
        if (next === y) return count + 1;
        if (next < y && !visit.has(next)) {
          visit.add(next);
          q.enqueue(next);
        }
      }
    }

    ++count;
  }

  return -1;
}