기초 알고리즘 1/2. 200 - 자료 구조 1
1158번. 요세푸스 문제

문제

1158번 문제 링크

solution 1

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

const N = input[0];
const K = input[1];

// 인원 배정
let queue = [];

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

let count = 1;

let ans = [];

while(queue.length > 0){
    let shiftedPeople = queue.shift();
    
    if(count % K === 0){
        ans.push(shiftedPeople);
    } else{
        queue.push(shiftedPeople);
    }
    
    count++;
}

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

큐를 사용하는 방법이다.
이 문제는 3번째 사람이 제거된 뒤, 그 뒤에 있는 사람부터 다시 3번째 사람을 찾아야한다.
그래서 일반적인 배열을 생각하고 진행하면 중간부터 생각이 꼬이기 시작한다.(필자가 그랬다)
또한, 일반적인 배열로 문제를 풀게 되면 3번째 사람이 배열을 넘어가게 될 경우 문제가 발생한다.

예시를 들어보자.

queue = [1,2,3,4,5,6,7]
N = 7
K = 3

이들 원소가 원의 형태로 앉아있다고 가정하고 시작하자.

3번을 제거하고 4번부터 시작하고
6번을 제거하고 2번을 제거해야하는데...

일반적인 배열처럼 생각하고 풀면 정말정말 꼬여버린다.
그래서 큐를 사용하는 방법으로 진행한다.

count를 1로 시작한다.

큐 구조를 사용하고 있으므로 가장 앞에 있는 데이터 1을 빼낸다.
이 때 count는 1이다.

우리가 가장 먼저 뽑아야하는 것은 3이다.
그러므로 1을 다시 큐의 맨 뒤에 넣는다.

count는 2이다.
2를 빼낸다. 이건 우리가 원하는게 아니다.
2를 다시 큐 맨 뒤에 넣는다.

count는 3이다.
3을 빼낸다. 이건 우리가 원하는 것이다!
따라서 3을 ans에 넣어놓고, 큐에는 빠진 상태로 유지한다.

다음에 뽑을 숫자 6은 어떻게 뽑을까...?
우선 현재 큐의 상태를 보자 [4,5,6,7,1,2] 이다.
아! 4가 가장 앞으로 와 있다.
3이 빠졌으므로 4부터 시작해야하는데 큐 구조 특성을 이용해서 간단하게 조건을 만족시켰다.

그럼 여기서부터 다시 위 과정을 반복하면 된다.
물론 count는 4부터 시작된다.
따라서, 6을 뽑을 때는 count가 6이 되어있을 것이다.
일반화하자면, count를 K로 나눴을 때 나머지가 0이 되면 그 숫자를 뽑아내면 되는 것이다.

count에 따라 큐에서 완전히 제거할지, 다시 뒤로 보낼지를 판별할 수 있게 된다.

solution 2

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

const N = input[0];
const K = input[1];

// 인원 배정
let queue = [...new Array(N)].map((item, index) => item = index + 1);

let count = 1;

let ans = [];

while(queue.length > 0){
    let shiftedPeople = queue.shift();
    
    if(count % K === 0){
        ans.push(shiftedPeople);
    } else{
        queue.push(shiftedPeople);
    }
    
    count++;
}

const answer = ans.join(", ");
console.log(`<${answer}>`);

혹시나 for문으로 queue를 만드는 것에서 시간초과가 발생할까봐
메서드들을 사용해서 queue를 만들어봤다.

참고 자료

이 분은 굉장히 문제를 잘 해석하시는 것 같다. 나도 저렇게 되고싶다!!!
참고 자료 1