Level 2 ) 숫자 변환하기

문제 설명

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

---

입출력 예 설명

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

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

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

풀이

dfs로 풀고자 했다.

1. stack에 현재 값과 연산 횟수를 함께 저장한다.
2. 현재 값이 y와 일치하면 연산 횟수를 return한다.
3. 방문 여부를 체크하여 반복 연산을 줄인다.
4. 현재 값에 n을 더한 값과 2를 곱한 값, 3을 곱한 값을 각각 stack에 푸시한다.
   (이때 값이 y보다 크면 푸시하지 않는다.)
5. 최소 연산 횟수를 구하기 위해 연산 횟수를 기준으로 내림차순 정렬한다.
6. 값을 찾지 못한 경우 -1을 return 한다.

스택을 이용해 풀려고 하니 최소 연산 횟수를 보장하지 못하는 문제가 발생했다.
따라서 연산 횟수를 기준으로 내림차순 정렬해 연산 횟수가 가장 적은 것을 먼저 확인하도록 했다.

그러나 정렬 과정에서 시간이 많이 소요되어 5개에서 시간 초과가 발생했다.

function solution(x, y, n) {
    let stack = [];
    stack.push([x,0]); // [현재 값, 연산 횟수]
    let visited = new Array(1000000).fill(0);
    
    while(stack.length){
        let [val, count] = stack.pop();
        if(val === y) return count;
        if(visited[val] === 1) continue;
        let newVal = [val + n, val * 2, val * 3];
        newVal.map(el => {
            if(el <= y) stack.push([el, count + 1]);
        });
      	// 연산 횟수를 기준으로 내림차순 정렬
        // 매번 정렬하려니 시간이 많이 걸림
        stack.sort((a,b) => b[1] - a[1]); 
        visited[val] = 1;
    }
    return -1;
}

풀이 개선

stack 대신 queue를 직접 구현하고 sort를 제거하여 통과했다.
(큐를 이용하면 정렬을 하지 않아도 자연스럽게 연산 횟수가 가장 적은 것을 먼저 확인하게 된다!)

class Queue {
    queue = [];
    front = 0;
    rear = 0;
    enqueue(value) {
        this.queue[this.rear] = value;
        this.rear++;
    }
    dequeue(){
        const returnVal = this.queue[this.front];
        delete this.queue[this.front++];
        return returnVal;
    }
    size(){
        return this.rear - this.front;
    }
}

function solution(x, y, n) {
    let queue = new Queue();
    queue.enqueue([x,0]);
    let visited = new Array(1000000).fill(0);
    
    while(queue.size()){
        let [val, count] = queue.dequeue();
        if(val === y) return count;
        if(visited[val] === 1) continue;
        let newVal = [val + n, val * 2, val * 3];
        newVal.map(el => {
            if(el <= y) queue.enqueue([el, count + 1]);
        });
        visited[val] = 1;
    }
    return -1;
}

⭐️ 큐를 직접 구현하지 않고 아래처럼 배열을 이용해 풀면 시간초과가 발생한다.

function solution(x, y, n) {
    let queue = [];
    queue.push([x,0]);
    let visited = new Array(1000000).fill(0);
    
    while(queue.length){
        let [val, count] = queue.shift();
        if(val === y) return count;
        if(visited[val] === 1) continue;
        let newVal = [val + n, val * 2, val * 3];
        newVal.map(el => {
            if(el <= y) queue.push([el, count + 1]);
        });
        visited[val] = 1;
    }
    return -1;
}