문제

백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 통해서 기념품을 받을 사람을 정하기로 결정했다.

게임이 시작하기 전에 모든 참가자 N명은 원을 이루어서 앉아있다. 다음, 1부터 N까지 번호가 적혀있는 티셔츠를 시계방향으로 입는다. 이 티셔츠는 게임에 사용되지 않으며, 게임을 쉽게 하기 위해서 입는 티셔츠이다.

게임은 단계로 이루어져 있으며, 첫 단계는 1단계이다. 각 단계가 시작될 때, 백준이는 어떤 참가자의 앞에 서있다. 그 다음, "하나"를 외친다. 그 다음, 시계 방향으로 다음 사람에게 이동하며 "둘"을 외친다. 이 과정은 t단계인 경우에 t3을 외칠 때 까지 진행한다. 예를 들어, 1단계에서는 1까지 외치며, 2단계에서는 8까지, 3단계에서는 27까지 외친다.

각 단계가 끝난 경우에, 백준이가 앞에 서 있는 사람은 게임에서 제외된다. (t단계인 경우에 t3을 외칠 때 앞에 있던 사람) 사람이 제거된 후에는 백준이는 시계 방향으로 다음 사람에게 이동한다. 1단계에서 백준이는 티셔츠 1번을 입고 있는 사람의 앞에 있다. 게임은 원에 한 명이 남을 때 까지 진행되며, 마지막 남은 사람이 기념품을 가져가게 된다.

참가자의 수 N이 주어졌을 때, 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 BOJ 캠프 참가자의 수 N (1 ≤ N ≤ 5,000)이 주어진다.

출력

첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.

예제 입력

3

예제 출력

2

내가 했던 풀이 방법

1. 참가자들을 1번부터 N번까지 담은 배열을 선언한다.
2. step을 1로 초기화하고 currentIndex를 0으로 한다.
3. participant 배열이 1이 될 때까지 제외할 사람의 번호를 계산하고, 해당 참가자를 participant에서 제거해준다. 제외할 사람은 currentIndex (현재 백준의 위치)에서 t^3을 한 값을 더해준 뒤, 남은 참가자의 수로 나눈 나머지가 된다. 매번 t^3에서 끝난 다음 사람부터 시작하므로, currentIndex를 더해주어야 하고, t^3번의 위치를 알기위해 t^3-1을 해준다. (index가 0부터 시작하므로) 제외한 뒤 currentIndex를 저장해주어야 한다. 사람이 제외되었기 때문에 participant.length 길이도 달라졌기 때문이다. 쉽게 생각하면 [1, 2, 3, 4, 5]에서 4가 제외된다 했을 때 [1, 2, 3, 5]에서 5부터 시작해야 하기 때문이라고 생각하면 된다. 제외를 한 뒤에 step도 1 증가시켜준다.
4. 3번이 끝나면 participant에는 한 명만 남게 된다. 그 한 명을 출력해주면 된다.

코드

var fs = require('fs');
var N = fs.readFileSync(0, 'utf-8').toString().trim();

N = Number(N);
let participant = Array.from({ length: N }, (_, index) => index + 1);

let step = 1;
let currentIndex = 0;
while (participant.length !== 1) {
  let removeIndex = (currentIndex + (step ** 3 - 1)) % participant.length;
  participant.splice(removeIndex, 1);
  currentIndex = removeIndex % participant.length;
  step++;
}

console.log(participant[0]);

회고

처음보자마자 queue를 생각했는데 shift/unshift 쓰면 시간 초과날 것 같았고, queue를 직접 구현하자니 위 방법이 떠올라서 위로 구현했는데 다행히 시간초과 같은 건 안 났다. 처음에는 splice도 시간초과가 걸릴 것 같아서 배열을 2개를 둬서 현재 참가자/제외대상이 아닌 참가자 배열로 하려고 했는데 결국 깊은 복사 때문에 slice를 써야해서 더 간단하게 splice로 구현했다.