요세푸스 문제0_11866

난이도 : **
소요시간 : 25분

문제 이해

• 1번부터 N번까지 원을 이루며 순서대로 앉아있다.
• 순서대로 K번째 사람을 제거한다.
• 남은 사람들로 다시 원을 만들어 같은 방식으로 K번째 사람을 제거한다.
• 모든 사람이 제거될때까지 위 행위를 반복한다.
• 제거되는 순서를 순열로 나타낸 것을 '요세푸스 순열'이라고 한다.

예제풀이

• 위 예제 처럼 N=7, K=3이라면 1번을 시작으로 3번째 순서에 있는 3이 제거가 된다.
• 그다음 순서는 4가 첫번째 순서가 3번째 순서에 있는 6이 제거가 된다.

아이디어

• 즉, k번째 사람이 제거된 후 k-1번째까지의 사람들이 뒤로 돌아간다고도 해석할 수 있다.
• 요소의 순서가 그대로 유지된채로 다시 뒤에 추가하는 것이므로 특정 인덱스에 접근하여 요소를 제거하는데 용이한 큐 자료구조를 선택하였다.

문제풀이

1. 큐 초기화:

   • Array.from을 사용하여 1부터 N까지의 숫자로 이루어진 배열(큐)을 초기화합니다.

   const queue = Array.from({ length: n }, (_, i) => i + 1);

2. 순환적 인덱스 계산:

   • (index + k - 1) % queue.length를 사용하여 제거할 사람의 인덱스를 계산합니다. 여기서 % queue.length는 큐의 길이를 벗어나지 않도록 인덱스를 순환시킵니다.

   index = (index + k - 1) % queue.length;

3. 요소 제거 및 결과에 추가:

   • splice 메서드를 사용하여 계산된 인덱스의 요소를 제거하고, 그 요소를 결과 배열에 추가합니다.

   result.push(queue.splice(index, 1)[0]);

4. 반복:

   • 큐가 빌 때까지 위 과정을 반복하여 모든 요소를 제거하고 결과 배열에 추가합니다.

   while (queue.length > 0) {
       // 인덱스 계산 및 요소 제거
   }

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split(" ");

const N = Number(input[0]);
const K = Number(input[1]);

// 큐를 초기화합니다. 큐의 길이는 n이고, 각 요소는 1부터 n까지의 숫자입니다.
const josephus = (n,k) => {
    const result = [];
    const queue = Array.from({ length : n }, (_, i) => i + 1);
    let index = 0;
    
    while(queue.length > 0){
        index = (index + k - 1) % queue.length;
        result.push(queue.splice(index, 1)[0])
        
    }
    
    

    return result;
}

const result = josephus(N, K);
console.log(`<${result.join(', ')}>`);

결론

큐를 이용하는 것과 순환적으로 인덱스에 접근하는 방식을 떠올려 코드로 풀어낼 수 있느냐가 관건인 문제라고 생각한다.