프로그래머스 - 숫자 변환하기 (JavaScript)

문제 설명

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

function solution(x, y, n) {
    
    class Node {
        constructor(data) {
          this.data = data;
          this.next = null;
        }
      }
    
    class Queue {
        constructor() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
    
        enqueue(data) {
            const node = new Node(data);
    
            if (this.tail === null) {
                this.head = node;
                this.tail = node;
            }
    
            else {
                this.tail.next = node;
                this.tail = node;
            }
    
            this.size++;
        }
    
        dequeue() {
            if (this.head === null) {
                return null;
            }
    
            const data = this.head.data;
            this.head = this.head.next;
    
            if (this.head === null) {
                this.tail = null;
            }
            
            this.size--;
            return data;
        }
    }
    
    const queue = new Queue();
    queue.enqueue(x);
    
    const visited = new Map();
    visited.set(x, 0);
    
    while (queue.size) {
        
        let num = queue.dequeue();
        
        if (num === y) {
            return visited.get(num);
        }
        
        if (!visited.has(num + n) && num + n <= y) {
            visited.set(num + n, visited.get(num) + 1);
            queue.enqueue(num + n);
        }
        
        if (!visited.has(num * 2) && num * 2 <= y) {
            visited.set(num * 2, visited.get(num) + 1);
            queue.enqueue(num * 2);
        }
        
        if (!visited.has(num * 3) && num * 3 <= y) {
            visited.set(num * 3, visited.get(num) + 1);
            queue.enqueue(num * 3);
        }
    }
    
    return -1;
}

 

위 풀이를 그림으로 나타내면 다음과 같다.

또한 다음과 같은 사항들을 고려해야 한다.

• 연산 횟수
• 데이터의 중복
• y보다 큰 데이터

 

연산 횟수

임의의 숫자에 대한 연산 횟수를 기록하기 위해 Map을 사용한다. 숫자를 key, 연산 횟수를 value로 하여 관리한다.

 

데이터의 중복

방문 체크를 통해 데이터의 중복을 제거함으로써 최소 연산 횟수를 보장할 수 있다. 이는 아래와 같은 조건을 만족하기 때문이다.

• 같은 레벨에 있는 노드들은 같은 연산 횟수를 가진다.
• BFS는 한 레벨을 모두 탐색한 후 다음 레벨로 넘어간다.

 

y보다 큰 데이터

y보다 큰 데이터는 큐에 삽입될 필요가 없으므로 조건을 추가한다.

---

shift 연산의 경우, 시간 초과가 나므로 queue를 구현하였다.

 

풀이 2) DP

function solution(x, y, n) {
    var answer = 0;
    let dp = Array.from({ length: y + 1 }, () => Infinity);
    dp[x] = 0;
    
    for (let i = x; i < y + 1; i++) {
        if (i + n <= y) dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
        if (i * 2 <= y) dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
        if (i * 3 <= y) dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
    }
    
    if (dp[y] === Infinity) {
        return -1;
    }
    
    return dp[y];
}

이미지 출처 : https://studyposting.tistory.com/93

한번의 루프는 같은 연산 횟수를 가진다. 세 가지 연산으로 나온 임의의 숫자(index)에 대해, Infinity로부터의 첫 갱신이 최소 연산 횟수이다.