[백준 11866번] 요세푸스 문제 0

 

 

이 문제는 원형 리스트로 입력받은 숫자까지 순서대로 리스트를 만든 후에, 찾은 인덱스에 대한 처리를 어떻게 할지가 조금 고민되는 문제였다.

 

나는 출력된 요소에 대해 삭제하는 방법을 택했고, JavaScript의 splice 함수를 사용했다.

 

그리고 삭제한 후의 규칙성을 확인해보면 아래와 같다.

 

배열 길이가 계속해서 감소하지만, 이전 배열과 다음 배열(감소된 배열)의 인덱스 차이가 2로 일정한 것을 확인했다. 

이는 입력값으로 받은 3-1의 값으로 나타낼 수 있게 된다.

 

따라서 단계에 따라 i * (3-1) 의 식을 사용하여 이 문제를 해결할 수 있게된다.

 

소스 코드

const input = require('fs')
	.readFileSync('/dev/stdin')
	.toString()
	.trim()
	.split('\n');

const [n, k] = input[0].split(' ').map(Number);

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

let index = 0;

while (queue.length > 0) {
	index = (index + k - 1) % queue.length;
	result.push(queue.splice(index, 1)[0]);
}

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