[백준] 1158 요세푸스 문제 Node.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)

출력

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

예제 입력 1

7 3

예제 출력 1

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

---

문제풀이

✅ 답안 #1: 메모리 18092 KB, 시간 2608 ms

1. count 변수를 초기화하여 현재 숫자의 순서를 추적한다. 처음에 count는 1로 시작한다.
2. while 루프를 통해 큐가 비어있을 때까지 반복한다. 큐가 비어있을 때 모든 숫자가 처리되었음을 의미한다.
3. 각 반복에서 큐에서 숫자를 하나 꺼내서 num에 저장한다.
4. count % K === 0를 확인하여 현재 순서가 K의 배수인지를 확인한다. 만약 count가 K의 배수이면, 해당 숫자는 요세푸스 순열에 추가되어야 한다. 그렇지 않으면 숫자는 큐의 뒤로 다시 들어간다.
5. count를 1 증가시켜 다음 숫자의 순서를 나타낸다.
6. 이 프로세스를 큐가 비어있을 때까지 반복한다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const queue = Array.from({ length: N }, (_, i) => i + 1);
const result = [];
let count = 1;

while (queue.length) {
  const num = queue.shift();
  if (count % K === 0) {
    result.push(num);
  } else {
    queue.push(num);
  }
  count++;
}
console.log(`<${result.join(', ')}>`);

✅ 답안 #2: 메모리 10660 KB, 시간 128 ms

1. target += K - 1은 현재 위치에서 K - 1을 더하는 연산을 수행한다. 이것은 요세푸스 순열에서 K번째 숫자를 찾기 위한 연산이다. 따라서 건너뛰어야 하는 숫자만큼 순열을 이동시킨다.
2. 그 다음 target %= nums.length는 target를 nums 배열의 길이로 나눈 나머지를 계산한다. 순열이 배열의 범위를 벗어나지 않도록 하기 위해서이다.
   • 예를 들어, nums.length가 7이라고 가정하고 target이 현재 8일 때, 7로 나눈 나머지는 1이다. 이것은 맨 앞부터 시작하는 배열의 인덱스를 나타내며, 순열의 첫 번째 위치를 가리킨다. 따라서 target을 다시 1로 설정하여 순열의 첫 번째 숫자를 건너뛴 후에 다음 숫자를 제거하는 과정을 반복한다. 이렇게 나머지 연산을 사용하면 target 값이 순열의 길이를 초과하지 않고 0부터 다시 시작하게 된다.
3. nums 배열에서 target 인덱스에 해당하는 요소를 추출하고, 추출한 요소를 result 배열에 추가한다. 이렇게 하면 요세푸스 순열이 순차적으로 생성된다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [N, K] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const nums = Array.from({ length: N }, (_, i) => i + 1);
const result = [];
let target = 0;
while (nums.length) {
  target += K - 1;
  target %= nums.length;
  result.push(nums.splice(target, 1)[0]);
}
console.log(`<${result.join(', ')}>`);