요세푸스 문제

문제

언어

  • JavaScript

문제 풀이 step 1

  • 큐를 이용해서 문제에서 주어진 조건대로 pop, push 하며 시뮬레이션하며 풀면 됩니다.
  • 하지만 index를 조작하는 방식으로 하면 pop, push를 안하면서 시뮬레이션하는 방식과 동일한 효과를 낼 수 있으므로, index를 조작하는 방식으로 합니다.
  • 실제 pop, push를 하는 것보다 index를 조작하는 것이 더 빠를 것 같습니다.
  • index에 (K-1) 값을 더하고 이 값이 현재 배열의 크기보다 더 크다면 %(MOD) 연산을 수행해 줍니다. (K-1인 이유는 현 위치에 있는 값을 세지 않고 넘어가기 때문입니다.)
  • 그리고 K번째 사람을 배열에서 제거합니다. 이를 반복하며 배열의 크기가 0이 될때까지 반복합니다.

소스 코드

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

const solution = (input) => {
	const [N, K] = input[0].split(" ").map(Number);
	const arr = Array.from({length: N}, (v, i) => i + 1);

	const res = [];
	let cursor = 0;
	while (arr.length > 0) {
		cursor += K - 1;
		if (cursor >= arr.length) cursor %= arr.length;

		res.push(arr[cursor]);
		arr.splice(cursor, 1);
	}

	return `<${res.join(", ")}>`;
};

console.log(solution(input));