📚
문제링크
문제
요세푸스 문제는 다음과 같다.
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 ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>
접근 방향 설명 📍
정말 예전에 풀어봤던 기억이 났던 문제! (아마 반년 전에 원형큐 어렵다 생각했었는데 이제 보니 ㅎㅎ 별거 없었던거 같다)
큐가 선입선출임을 다시금 상기하고, 문제를 보면 처음과 끝이 연결되었다고 생각하면 된다. 원을 똑 잘라서 쭉 펴면 직선이 되는 논리를 생각하면 편하다 ⭕️ => ------
원형 큐를 직선으로 바꾸어 생각해보면, 제일 앞에 있는 사람 (1번)은 7번 옆에 앉게 되므로, 1번이 7번 뒤로, 2번이 1번 뒤로, 3번에 2번 뒤로 가도 원은 그대로 유지된다
(1번 옆에는 2번과 7번이 앉게 되는데 => 뒤로 옮겨도 1번 옆의 사람은 변하지 않음)
그렇기 때문에, 특정 순서의 사람이 아니라면 뒤로 보내서 원형자리는 유지하되! K번쨰 사람은 shift로 빼주기!
풀이 코드 해석
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "/input.txt";
let input = fs.readFileSync(__dirname + filePath).toString().split(" ");
// 백준 제출용 코드
// let input = fs.readFileSync(filePath).toString().split("\n");
let N = +input[0]; // 사람 수
let K = +input[1]; // 제거할 순서
let idx = K; // 순서를 결정할 인덱스
let circle = []; // 원형큐를 나타낼 직선 배열
let ans =[]; // 빠져나가는 사람을 담을 배열
for(let i =1; i <= N; i++){ // 사람 앉히기
circle.push(i)
}
while(circle.length !== 0) {
if (idx === 1) { // 특정 순서인 경우에, 원형큐에서 빼서 => ans에 넣기 / 그 뒤로 K 번째 사람을 뻬기 위해서 idx 초기화
ans.push(circle.shift())
idx = K
}
else { // K번째 순서가 아닌 경우 뒤로 보내기 (원형큐 유지) + 순서 - 1
circle.push(circle.shift());
idx -=1
}
}
console.log(`<${ans.join(', ')}>`);
풀이 과정에서 새롭게 느낀점(배운점)
☁️ shift와 pop 구분
부끄러운 이야기이지만.. 처음에 shift를 넣을 자리에 pop을 넣어버렸다. 이번에만 헷갈릴거라고 안일하게 생각하지 말고 타산지석 삼아서 이런 실수 하지 말아야지!
shift -> 제일 첫번째 요소를 삭제 (큐) .. 선입선출
pop -> 제일 마지막 요소를 삭제 (스택) .. 후입선출
☁️ 백틱 사용하기!
출력시, 백틱 사용해서 보다 직관적이고 간결하게 코드짜기 🫡
