.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
구현, 큐, 211103
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
Plain Text
복사
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>
Plain Text
복사
My solution
(7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>
1 2 3 4 5 6 7
// 먼저 3번째인 3을 제거한다. 제거된 사람의 다음 사람부터 순서를 센다.
1 2 4 5 6 7
// 이 된다. 3번째는 6이다.
1 2 4 5 7
// 이 된다. 7부터 시작하니까 돌아서 3번째는 2이다.
1 4 5 7
// 3번째는 7이다.
1 4 5
// 3번째는 5이다.
1 4
// 3번째는 1이다.
4
K번째마다 사람을 제거하겠지만 사람을 제거하는 횟수가 아니라 그 사람을 찾기 위해서 다른 사람들을 이동시키는횟수까지 알아야했다. 그래서 반복횟수가 명확하지 않았기 때문에 while문으로 한번 감싸주었다. 결과적으로 모든 사람을 제거해주면 끝나기 때문에 q.length로 두어 큐의 길이가 0이 되면 while문이 멈추게 했다.
그리고 내부에서 for문으로 K번째 사람을 찾기 위해서 K번 반복하면서 K번째가 되었을 때만 answer 배열에 해당 사람을 집어넣었다. 나머지 경우는 제거하면 안되기 때문에 큐에 push 연산으로 뒤에 붙여주었다.
소스코드
function solution(i) {
let answer = [];
const input = i
.toString()
.trim()
.split(" ")
.map((v) => parseInt(v)); // +v 가 낫다. 실수 -> 정수 변환에 비용이 더 든다.
let q = [...Array(input[0])].fill(0).map((_, i) => i + 1);
let K = input[1];
while (q.length) {
for (let i = 0; i < K; i++) {
if (i === K - 1) answer.push(q.shift());
else q.push(q.shift());
}
// for loop >> forEach
q.forEach((v,i)=>{
if (i === K - 1) answer.push(q.shift());
else q.push(q.shift());
return;
}) // 안된다. shift()연산이 있기 때문
// 요소 "four"가 이제 배열의 이전 위치에 있으므로 "three"를 건너뜁니다.
forEach()는 반복하기 전에 배열의 복사본을 만들지 않습니다.
// https://stackoverflow.com/questions/36716409/inconsistent-results-when-using-foreach-and-shift
}
console.log(`<${answer.join(", ")}>`);
return `<${answer.join(", ")}>`;
}
test("solution", () => {
expect(solution("7 3")).toStrictEqual("<3, 6, 2, 7, 5, 1, 4>");
});
JavaScript
복사
