프로그래머스: 숫자 변환하기(javascript, deque, bfs)

BFS를 이용해 푼 문제이다. 처음에 BFS로만 풀려 했으나 계속 시간초과가 나서 백준 소꿉놀이처럼 미리 배열을 선언해두고, 시작점을 1로 해둔다. 그리고 방문안한 점을 방문할 때만 이전 지점에 1을 더해서 연산 횟수를 기록하는 방식이다.

 

글까지 써가며 기록하게 된 이유는 자바스크립트의 배열은 shift와 unshift연산이 모두 되는 deque이기에 bfs를 쓸 때 그냥 배열에 저장했었는데 테스트 케이스 두개가 계속 시간초과가 나서 자료구조를 다른 사람이 구현해놓은 deque을 사용했는데 훨씬 빠르게 통과돼서 놀랐었다. 왜냐하면 보통 내장함수나 내장 자료구조보다 잘 구현하기는 힘들기 때문이다. 

 

앞으로 deque이나 queue자료구조가 필요한 알고리즘 문제는 자료구조를 직접 구현해서 써야겠다.

 

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

class Deque {
    constructor() {
        this.init();
    }

    init() {
        this.count = 0;
        this.front = null;
        this.rear = null;
    }

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

        if (!this.front) {
            this.front = node;
            this.rear = node;
        } else {
            this.front.prev = node;
            node.next = this.front;
            this.front = node;
        }

        this.count += 1;
        return this.count;
    }

    shift() {
        if (this.count === 0) return null;

        const value = this.front.value;

        if (this.count === 1) {
            this.init();
        } else {
            this.front = this.front.next;
            this.front.prev = null;
            this.count -= 1;
        }

        return value;
    }

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

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

        this.count += 1;

        return this.count;
    }

    pop() {
        if (this.count === 0) return;

        const value = this.rear.value;

        if (this.count === 1) {
            this.init();
        } else {
            this.rear = this.rear.prev;
            this.rear.next = null;
            this.count -= 1;
        }

        return value;
    }

    getValue(idx) {
        if (idx >= this.count) return;
        let node = this.front;

        for (let i=1; i<=idx; i++) {
            node = node.next;
        }

        return node.value;
    }

    get array() {
        let arr = [];
        let node = this.front;

        for (let i = 0; i < this.count; i++) {
            arr.push(node.value);
            node = node.next;
        }

        return arr;
    }

    get length() {
        return this.count;
    }
}

function BFS(x,y,n){
    let num = new Array(1000001).fill((0))
    num[x] = 1
    let queue = new Deque()
    queue.push(x)
    while(queue.length){
        let a = queue.shift()
        if (a+n <= y && !num[a+n]){
            num[a+n] = num[a]+1
            queue.push(a+n)
        }

        if (2*a <= y && !num[a*2]){
            num[2*a] = num[a]+1
            queue.push(2*a)
        }

        if (3*a <= y && !num[a*3]){
            num[3*a] = num[a]+1
            queue.push(3*a)
        }
    }
    return num[y]-1
}

function solution(x, y, n) {
    return BFS(x,y,n)
}