[바미] 카드2

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input, 10);

class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.back = 0;
    }

    push(x) {
        this.queue[this.back++] = x;
    }

    shift() {
        if (this.front !== this.back) {
            const value = this.queue[this.front];
            delete this.queue[this.front];
            this.front++;
            return value;
        }
        return -1;
    }

    size() {
        return this.back - this.front;
    }

    isEmpty() {
        return this.size() === 0;
    }
}

const queue = new Queue();

for (let i = 1; i <= N; i++) {
    queue.push(i);
}

while (queue.size() > 1) {
    queue.shift(); // 제일 위에 있는 카드를 버린다.
    queue.push(queue.shift()); // 제일 위에 있는 카드를 제일 아래로 옮긴다.
}

console.log(queue.shift()); // 마지막으로 남는 카드를 출력한다.

문제 해설

이 문제는 큐를 이용하여 카드의 순서를 관리하면서, 주어진 동작을 반복하여 마지막에 남는 카드를 찾는 문제입니다.

 

마찬가지로 Queue라는 클래스내에 기능을 만들어 해결했고, 먼저 제일 위에 있는 카드를 버리고, 그 다음 제일 위에 있는 카드를 제일 아래로 옮기는 과정을 큐의 길이가 1이 될 때까지 동작을 반복하여 돌아가는 형태로 매우 간단합니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

각 shift와 push 연산이 O(1)시간에 수행되기 때문에 N개의 카드에 대해 최대 2N 번의 연산이 필요하므로 전체 시간 복잡도는 O(N)이 됩니다.

 

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

여기에선 큐를 저장하기 위한 공간만 필요하므로, 공간 복잡도는 O(N)가 됩니다.