문제

https://www.acmicpc.net/problem/1158

유대인 역사가인 요세푸스가 겪은 경험을 바탕으로 만들어진 문제라고한다

유대-로마 전쟁때 41명의 동료 병사들이 로마군에게 포위됐는데
동료들은 로마군의 손에 죽을바엔 스스로 목숨을 끊겠다고 다짐하고 집단자살을 하기로 했다.
근데 직접 자살하는건 어려웠는지 첫번쨰 사람은 두번째를, 세번째는 네번째를, ...,
39번째는 40번째를, 41번째는 첫번째 사람을 죽이는 식으로 자살했다.
하지만 요세푸스는 동료들의 뜻에 반대하고 살고 싶어서
수학적 논리력을 발휘해 끝까지 살기 위한 자리를 찾아서 결국 살아남아 항복했다.

이때 사람들이 제거되는 순서를 구하는 문제다. 위의경우에 2, 4, 6, ... 이 된다.

입력

• N과 K가 첫째줄에 주어진다.
  -이때, 1 ≤ K ≤ N ≤ 5,000

출력
사람들이 제거되는 (N, K)-요세푸스 순열을 <2, 4, 6...> 과 같은 형식으로 출력한다.

정답코드1

const stdin = require('fs').readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

class L {
  list = { now: 0, next: null };
  head = this.list;
  tail = this.list;
  beforeNode = this.head;
  nowNode = this.head;
  len = 0;

  push(number) {
    this.tail.next = { val: number, next: null };
    this.tail = this.tail.next;
    this.tail.next = this.head;
    this.len++;

    if (this.head.now === 0) {
      this.head = this.head.next;
    }
  }
  pop(index) {
    for (let i = 0; i < index - 1; i++) {
      this.beforeNode = this.beforeNode.next;
    }
    this.nowNode = this.beforeNode.next;
    this.beforeNode.next = this.nowNode.next;
    this.len--;
    return this.nowNode.val;
  }
}
const solution = (N, K) => {
  const node = new L();
  const result = [];

  for (let i = 1; i <= N; i++) {
    node.push(i);
  }
  while (node.len > 0) {
    result.push(node.pop(K));
  }
  return `<${result.join(', ')}>`;
};

const [N, K] = input();
console.log(solution(N, K));

정답코드1 설명

링크드리스트를 사용해 구현한 코드다.
1 ~ N까지 숫자가 들어가 있는 링크드리스트를 생성후에
K번째 숫자를 계속 pop하고 그 결과를 출력한다.

정답코드 2

const stdin = require('fs').readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

const [n, k] = input();
const arr = Array.from({ length: n }, (_, i) => i + 1);
const result = [];
let pick = 0;

while (arr.length) {
  pick += k - 1;
  if (pick >= arr.length) pick %= arr.length;
  result.push(+arr.splice(pick, 1));
}

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

정답코드2 설명

순환큐를 간단하게 구현한 모습이다.
while문을 arr이 빌때까지 돈다.

돌때마다 pick에 k-1을 더해주는데 pick은 제거되는 숫자의 위치다.
k를 더해주는게 아니라 k-1을 더해주는 이유는 현재 k의 숫자가 제거되면
그 앞에있던 숫자들은 당겨지기 때문에 k-1을 더하면 현재 위치가 구해진다.

if (pick >= arr.length) pick %= arr.length;

위의 코드를 적음으로 인해 순환큐가 구현되는데
다음 pick이 arr의 길이보다 클경우 pick = pick % arr의 길이가 된다.

만약 N=7, K=3이고 현재 pick이 result에 3,6이 들어갔다면
현재 pick = 6이다. 6은 현재 arr의 길이인 5보다 길기때문에
pick = pick % arr = 6 % 5 = 1

이 다음에는 arr[1]의 숫자를 제거하면 된다.

끗!