[백준 알고리즘] 1158번: 요세푸스 문제 (JavaScript / JS / 자바스크립트)

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

 

출력

예제와 같이 요세푸스 순열을 출력한다.

 

예제 입력

7 3

 

예제 출력

<3, 6, 2, 7, 5, 1, 4>

---

문제 접근

예제 입출력인 [7,3]의 경우, 7이 원을 이루고 있는 사람들의 수, 3이 순번을 의미한다.

3번째에 해당하는 사람을 계속해서 없애는 과정인데, 1 ~ 7에서 처음 3이 삭제된다면 4부터 다시 순번을 센다.

예제의 경우, 제거 순서는 아래와 같다.

1, 2, 3, 4, 5, 6, 7 --> 3 제거
1, 2, 3, 4, 5, 6, 7 --> 6 제거
1, 2, 3, 4, 5, 6, 7 --> 2 제거
1, 2, 3, 4, 5, 6, 7 --> 7 제거
1, 2, 3, 4, 5, 6, 7  --> 5 제거
1, 2, 3, 4, 5, 6, 7   --> 1 제거
1, 2, 3, 4, 5, 6, 7   --> 4 제거

 

위 과정을 프로그래밍으로 구현하면 된다.

3이 제거되고 나면 첫 번째 index는 4가 되어야 하므로,

 

1, 2, 3, 4, 5, 6, 7 --> 3 제거
4, 5, 6, 7, 1, 2--> 4가 first index가 된다. 6이 3번째이므로 제거

 

위와 같이 배열의 구조가 변해야 한다.

이는 큐(Queue)로 구현할 수 있다.

큐는 선입선출 구조로, 시작 부분으로는 데이터가 삭제되기만 하고 끝 부분으로는 데이터가 삽입되기만 한다.

1, 2, 3번 index에 해당하는 요소를 삭제 후, 1, 2번 요소만 끝 부분으로 다시 삽입하는 알고리즘을 구현하면 될 것 같다.

 

정답 코드

//Queue 구현
class Queue {
    constructor() {
        this.queue = [];
    }

    enqueue(item) {
        this.queue.push(item);
    }

    dequeue() {
        return this.queue.shift();
    }

    isEmpty() {
        return this.queue.length === 0;
    }

    front() {
        return this.queue[0];
    }

    clear() {
        this.queue = [];
    }

    length() {
        return this.queue.length;
    }
}

Queue를 따로 구현했다.

 

// 백준 1158: 요세푸스 문제

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin
});

rl.question('', (input) => {
    input = input.trim().split(' ');
    input = input.map(item => parseInt(item));
    void answer(input);
    rl.close();
});

function answer(input) {
    const n = input[0]; //사람 수
    var k = input[1]; //순번

    //Queue 생성
    const queue = new Queue();

    for(i=1; i<=n; i++){
        queue.enqueue(i);
    }

    //삭제되는 순서를 저장할 배열 생성
    const arr = [];

    for(i=0; i<n; i++){ 
        //k>n or k==n인 경우 처리
        k = k%n;
        if(k == 0){
            k = n;
        }
        for(j=0; j<k; j++){  //k번째 인덱스까지 삭제 -> dequeue를 k번 + enqueue는 k-1번
            var temp = queue.dequeue();
            if(j!=k-1){  //k번째 인덱스가 아니라면 (큐에 다시 추가)
                queue.enqueue(temp);
            }
            else{        //k번째 인덱스라면 (큐에 다시 추가하지 않음. 답안 리스트에 추가)
                arr.push(temp);
            }
        }
    }

    console.log(`<${arr.join(", ")}>`);
}

 

삭제할 요소를 찾는 과정은 아래의 과정으로 이루어진다.

{

1. k번째 인덱스까지 모두 삭제

2. k번째 인덱스는 별도 배열에 저장

3. 1, 2번째 인덱스는 다시 queue에 넣는다.

}                 

-> n만큼 반복

 

출력은 백틱과 템플릿 리터럴, join 함수를 사용하면 간단히 할 수 있다.

 

for(i=0; i<n; i++){ 
        //k>n or k==n인 경우 처리
        k = k%n;
        if(k == 0){
            k = n;

이 부분 때문에 오답 처리가 되었었는데, k>n or k==n인 경우(ex - 3,7 또는 3,3)에는 따로 처리를 해 주었다.

 

---

1158번: 요세푸스 문제