[BOJ] 2346번: 풍선 터뜨리기 자바스크립트 풀이 (메모리 초과)

1. 문제

https://www.acmicpc.net/problem/2346

 

 

2. 풀이과정

의사코드

1. 1번 풍선을 삭제한 후, 3칸 뒤로 이동한다.       [1]
2. 4번 풍선을 삭제한 후, 3칸 앞으로 이동한다.   [1, 4]
        1번이 없으므로 5번으로 이동된다.
3. 5번 풍선을 삭제한 후, 1칸 앞으로 이동한다.    [1, 4, 5]
        4번이 없으므로 3번으로 이동된다.
4. 3번 풍선을 삭제한 후, 1칸 뒤로 이동한다.       [1, 4, 5, 3]
        4번이 없으므로 5번으로 이동된다.
        5번이 없으므로 1번으로 이동된다.
        1번이 없으므로 2번으로 이동된다.
5. 2번 풍선을 삭제한다.                                     [1, 4, 5, 3, 2]

 

리스트의 앞, 뒤에서 삽입 삭제가 이루어진다. 리스트는 점점 줄어들며 회전한다.

즉, 앞 뒤를 동시에 다뤄야하는 회전 구조로 덱을 사용하는 것이 적합하다 판단했다.

 

전체코드

const readline = require('readline');

(async () => {
    const rl = readline.createInterface({ input: process.stdin });
    
    const input = [];
    for await (const line of rl) {
        input.push(line.trim());
        if (input.length === 2) rl.close();
    }
    
    class Deque {
        constructor() {
            this.items = {};
            this.front = 0;
            this.rear = 0;
        }
        
        push_front(item) {
            this.front--;
            this.items[this.front] = item;
        }
        push_rear(item) {
            this.items[this.rear] = item;
            this.rear++;
        }
        pop_front() {
            if (this.isEmpty()) return undefined;
            const item = this.items[this.front];
            delete this.items[this.front];
            this.front++;
            return item;
        }
        pop_rear() {
            if (this.isEmpty()) return undefined;
            this.rear--;
            const item = this.items[this.rear];
            delete this.items[this.rear];
            return item;
        }
        isEmpty() {
            return this.size() === 0;
        }
        size() {
            return this.rear - this.front;
        }
    }
    
    const N = Number(input[0]);
    const nums = input[1].split(' ').map(Number);
    
    const deque = new Deque();
    for (let i = 0; i < N; i++) {
        deque.push_rear([i + 1, nums[i]]);
    }
    
    const result = [];
    while (!deque.isEmpty()) {
        const [idx, move] = deque.pop_front();
        result.push(idx);
        
        if (deque.isEmpty()) break;
        
        if (move > 0) {
            for (let i = 0; i < move - 1; i++) {
                deque.push_rear(deque.pop_front());
            }
        } else {
            for (let i = 0; i < -move; i++) {
                deque.push_front(deque.pop_rear());
            }
        }
    }
    
    console.log(result.join(' '));
})();

메모리 초과

 

백준에서 코드를 제출하면 메모리 초과가 발생한다 ㅜㅜ..

게시판 보면 node.js로 성공한 사람이 거의 없을 정도로 드뭄..  언어별 메모리 사용이 다르다는데 node.js로 풀기엔 메모리가 너무 작은 것 같다 !!! 👿