[바미] 요세푸스 문제 0

문제

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split(' ');
const N = parseInt(input[0], 10);
const K = parseInt(input[1], 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();
const result = [];

// 1부터 N까지 큐에 삽입
for (let i = 1; i <= N; i++) {
    queue.push(i);
}

while (!queue.isEmpty()) {
    // K-1번 요소를 큐의 뒤로 이동
    for (let i = 0; i < K - 1; i++) {
        queue.push(queue.shift());
    }
    // K번째 요소를 결과 리스트에 추가
    result.push(queue.shift());
}

console.log(`<${result.join(', ')}>`);

문제 해설

요세푸스 문제는 원형으로 배열된 사람들 중 매 K번째 사람을 제거하는 문제입니다. \

 

코드가 동작하는 형태는 아래와 같습니다.

• 초기에는 1부터 N까지의 숫자를 큐에 넣어줍니다.
• 큐를 사용하여 순서를 유지하고, K번째 사람을 제거한 뒤 결과 리스트에 저장해줍니다.
• 큐에서 K-1번 요소를 꺼내어 큐의 뒤로 다시 넣고, K번째 요소를 제거하여 결과 리스트에 추가합니다.
• 이 과정을 큐가 빌 때(모든 사람이 제거될 때)까지 반복해줍니다.
• 그 후 최종 결과 리스트를 '< , >' 형식으로 출력해줍니다.

시간 복잡도

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

 

각 제거 연산은 O(1) 시간에 처리됩니다.

N명이 제거될 때까지 총 N개의 제거 연산이 필요하므로 전체 시간 복잡도는 O(N)이 됩니다.

공간 복잡도

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

 

큐를 저장하기 위한 공간과 결과 리스트를 저장하기 위한 공간이 필요하므로, 공간 복잡도는 O(N)이 됩니다.