개발
[백준] 11866번 - 요세푸스 문제 0
문제 탐색하기
1) 문제 분석
N : 사람의 수, K : 제거할 번째 사람
N명 중 K번째 인원을 제거
제거 후 남은 인원으로 이 과정을 반복
N명의 사람이 모두 제거될 때까지 계속
2) 가능한 시간복잡도
(1) 입력 처리
N, K 입력: O(1)
(2) 배열 초기화
1부터 N까지 배열 생성: O(N)
(3) 요세푸스 순열 계산
array에서 splice()로 한 명씩 제거 (N번 반복)
splice는 최악의 경우 O(N) (인덱스에 따라 shift 발생)-> 총 N번 반복 → O(N^2) 시간 소요 가능성 있음
(4) 결과 출력
result 배열 join 출력: O(N)
(5) 전체 시간복잡도: O(N의 제곱 )
(이유: splice의 내부 동작이 N번 반복되며 O(N) 시간 소모)
3) 알고리즘 선택 이유
이 문제는 원형 순열에서 K번째 사람을 차례로 제거하는 문제로, 인덱스를 계속해서 순환해야 하고, 제거된 요소는 다시 탐색하지 않아야 한다.
이를 위해
배열을 사용하여 사람들의 번호를 순서대로 저장하고,
현재 인덱스를 (idx + K - 1) % array.length로 갱신해가며 제거를 반복했다.
배열의 특정 인덱스를 제거할 때 `splice()`를 사용했기 때문에, 시간복잡도는 O(N^2)이지만, N ≤ 1,000 범위에서는 충분히 실시간으로 처리 가능한 수준이다.
따라서 이 문제는 순차 탐색과 제거가 반복되는 특성상, 큐 혹은 배열 기반의 시뮬레이션 알고리즘이 적합하며, 직관적이고 구현도 간단한 배열 방식이 가장 적절하다.
코드 설계하기
1. 실행 구조
1) N과 K 입력
한 줄로 입력된 두 정수 N, K를 공백 기준으로 분리하고 숫자로 변환하여 각각 저장한다.
N: 사람 수, K: 제거할 순서 기준이 된다.
2) 사람 번호 배열 초기화
1번부터 N번까지 번호를 가진 사람들을 배열(array)에 저장한다.
이는 원형 구조를 단순 배열로 시뮬레이션하기 위한 단계다.
3) 제거 순서 계산 및 저장
현재 인덱스(idx)에서 시작해 (idx + K - 1) % array.length의 규칙으로 다음 제거 대상을 찾는다.
해당 인덱스에 있는 사람을 splice()로 제거하면서, 동시에 result 배열에 제거된 번호를 추가한다.
이 과정을 array가 빈 배열이 될 때까지 반복한다.
4) 결과 출력
최종적으로 제거된 사람의 순서(result)를 <숫자, 숫자, ...> 형태로 출력한다.
join(', ')을 활용해 형식에 맞는 문자열을 만든다.
2. 고민이 되었던 부분
: 원형 구조의 순차적인 제거를 어떻게 구현할지 고민이 가장 컸다.
이 문제는 단순히 배열에서 값을 제거하는 것이 아니라, “K번째 사람을 계속 제거하며 순환하는 구조”를 구현해야 했기 때문에, 다음과 같은 점들을 중점적으로 설계했다.
1) 첫 번째, 인덱스 순환을 고려한 구현
단순히 배열을 순회하는 것이 아니라,
현재 위치에서 K번째를 정확하게 찾기 위해 (현재 위치 + K - 1) % 배열 길이를 사용했다.
이로써 배열이 줄어들어도 인덱스 초과 없이 계속 순환하도록 처리할 수 있었다.
2) 두 번째, 제거와 결과 기록을 동시에 처리
배열에서 값을 제거하기 위해 splice()를 사용했으며,
제거된 사람 번호는 동시에 result 배열에 저장하였다.
splice()는 제거된 요소를 배열로 반환하기 때문에 [0]으로 실제 값을 꺼내는 방식으로 코드를 간결하게 유지했다.
3) 세 번째, 출력 형식에 대한 처리
출력 형식이 <3, 6, 2, 7, 5, 1, 4>처럼 요구되었기 때문에,
join(', ')을 활용해 결과 배열을 문자열로 변환한 후, < >로 감싸 최종 출력하였다.
이와 같은 구조 덕분에 코드가 간단하면서도 문제 조건을 정확하게 충족할 수 있었고, 특히 순환 인덱스를 계산하는 로직과 제거된 사람의 순서를 잘 관리하는 것이 핵심이었다.
정답 코드
// 사용 언어 : Javascript
// 입력을 파일에서 읽어옴
const fs = require('fs');
const [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);
// 1번부터 N번까지 사람을 배열에 저장
const array = [];
for (let i = 1; i <= N; i++) {
array.push(i);
}
// 제거되는 순서를 저장할 배열
const result = [];
let idx = 0;
// 사람이 모두 제거될 때까지 반복
while (array.length > 0) {
// K번째 사람의 인덱스를 계산
idx = (idx + K - 1) % array.length;
// 해당 사람을 제거하고 결과에 추가
// array.splice(idx, 1)[0]:
// (1) splice(idx, 1) : 배열 array에서 idx 번째 요소 1개를 제거하고, 그 제거된 요소를 배열로 반환.
// (2) [0] : splice()가 반환한 배열의 첫 번째 요소를 꺼냄.
result.push(array.splice(idx, 1)[0]);
}
// 결과를 형식에 맞게 출력
console.log(`<${result.join(', ')}>`);마무리하며
처음 이 문제를 접했을 때는 단순히 K번째 사람을 차례대로 제거하는 시뮬레이션 문제라고 생각했다. 하지만 직접 구현을 시작하고 나서야, 원형 구조에서 인덱스를 순환하며 정확히 제거 대상을 계산하는 로직이 핵심이라는 걸 깨달았다. 특히 배열의 길이가 계속 줄어들기 때문에, 매 단계에서 인덱스를 어떻게 갱신하느냐가 전체 흐름을 좌우하는 중요한 포인트였다.
이번 문제를 풀면서 다시금 느낀 건, 문제를 코드로 구현하는 과정은 단순한 지시사항 수행이 아니라, 문제 상황의 구조를 정확히 이해하고 그 흐름을 코드로 옮기는 작업이라는 점이었다. 눈에 보이는 패턴을 그대로 옮기기보다는, 그 이면에 숨은 규칙과 흐름을 파악하는 힘이 더 중요하다는 걸 실감했다.
또한, 결과만 맞추는 것에 그치지 않고, 코드의 효율성과 가독성, 구조적 설계까지 고민하는 자세가 문제 해결력을 키우는 핵심 요소라는 걸 느꼈다.