백준 1158 요세푸스

요세푸스? 처음들어보는 이름이었는데 문제를 읽고 조금 고민해보니 어디선가 접해본적 있는 문제였다.

제한사항에 주어진 최대값이 5000까지라 시간복잡도를 고려하지 않아도 된다고 생각했는데 오산이었다.

처음작성하는 코드는 다음과 같다.

const fs = require('fs');
let input = fs
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split(' ')
  .map((v) => +v);
const [N, K] = input;

const queue = Array.from({ length: N }, (_, i) => i + 1);
let answer = '';

let cnt = 0;
while (queue.length) {
  if (cnt === K - 1) {
    answer += `${queue[0]}, `;
    queue.splice(0, 1);
    cnt = 0;
  } else {
    for (let i = 0; i < K - 1; i++) {
      queue[queue.length] = queue[0];
      queue.splice(0, 1);
      cnt++;
    }
  }
}
answer = answer.slice(0, -2);
console.log(`<${answer}>`);

cnt라는 변수를 선언하고 반복문을 돌면서 처음 나오는 요소를 맨뒤에 넣고 splice 메서드로 삭제하고 카운트를 올려서 카운트가 K가 되는 순간 answer 변수에 더해주고 또 splice하여 삭제하도록 구현하였다.

하지만 splice 메서드 때문인지 5000으로 테스트해보니 정말 오래걸렸다..

그래서 리팩토링하여 코드를 수정했다.

const fs = require('fs');
let input = fs
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split(' ')
  .map((v) => +v);
const [N, K] = input;

const queue = Array.from({ length: N }, (_, i) => i + 1);
let answer = '';

while (queue.length) {
  for (let i = 0; i < K; i++) {
    queue.push(queue.shift());
  }

  answer += `${queue.pop()}, `;
}
answer = answer.slice(0, -2);
console.log(`<${answer}>`);

push, pop메서드는 O(1) 시간 복잡도를 가지기 때문에 적극활용해도 될 거 같고 splice의 사용을 억제하여 작성했다.

splice 를 최대한 억제해보자.