[백준] 요세푸스 문제 1158 (Silver4) - C++

 문제 링크

https://www.acmicpc.net/problem/1158

 

---

📌 문제 요약

• 1부터 N까지 번호가 붙은 사람들이 원형으로 앉아 있다.
• 매번 K번째 사람을 제거한다.
• 제거되는 순서를 < > 형식으로 출력한다.

전형적인 시뮬레이션 문제처럼 보이지만,
이 문제의 본질은 “원형 구조를 어떻게 표현할 것인가”에 있다.

---

💡 접근 아이디어

처음 떠올릴 수 있는 방법은 여러 가지다.

• 배열 + 인덱스 계산
• 원형 연결 리스트
• 수학적 점화식

하지만 이 문제에서 가장 직관적이고 실수 없는 방법은 큐(queue) 를 사용하는 것이다.

핵심 관찰

“원형(Cycle)은 선입선출(FIFO)의 재입력이다.”

• 맨 앞 사람을 꺼내서 다시 맨 뒤로 보내면
• 사람들은 자연스럽게 원형으로 회전한다

굳이 % 연산으로 인덱스를 계산하거나,
복잡한 자료구조를 만들 필요가 없다.

---

구현 코드 (C++)

#include <bits/stdc++.h>
//ctr + alt +n

using namespace std;

int main(){
    int n, k;
    cin>>n>>k;

    queue<int> q;
    vector<int> v;
    for(int i=0;i<n;i++){
        q.push(i+1);
    }
    int tmp;
    while(!q.empty()){
        for(int i=0;i<k-1;i++){
            tmp=q.front();
            q.pop();
            q.push(tmp);
        }
        tmp=q.front();
        v.push_back(tmp);
        q.pop();
    }
    cout<<"<";
    for(int i=0;i<v.size()-1;i++){
        cout<<v[i]<<", ";
    }
    cout<<v.back()<<'>';
 

    return 0;
}

 

---

 이 풀이가 깔끔한 이유

1.  순환은 FIFO의 재입력이다

• pop() → push()는
  원형 컨베이어 벨트를 한 칸 돌리는 것과 같다
• 큐 하나만으로 원형 구조를 자연스럽게 표현

👉 원형 리스트, % 연산 없이도 문제 해결 가능

---

2. 보류와 확정의 분리

이 문제를 이렇게 생각하면 훨씬 단순해진다.

• K-1명 → 아직 제거 대상 아님 → 뒤로 보냄 (보류)
• K번째 → 제거 대상 → 영구 이탈 (확정)

 

for(int i = 0; i < k-1; i++){ q.push(q.front()); q.pop(); }

 

👉 “삭제”보다
👉 “삭제될 사람을 찾을 때까지 기다리는 과정”이 핵심

---

3. 인덱스 관리 대신 상태 관리

배열로 풀면 항상 이런 고민을 하게 된다.

• 지금 인덱스가 몇이지?
• 하나 삭제했으니 뒤에 것들 다 당겨야 하나?
• off-by-one 에러 안 났나?

큐를 쓰면 이런 고민이 사라진다.

“내가 사람을 찾아다니는 게 아니라,
사람들이 내 앞(front)을 지나가게 만든다.”

• 나는 오직 front()만 본다
• 인덱스 계산 자체가 필요 없음

👉 중간 삭제가 반복되는 문제에서 큐는 실수 방지용 도구

요세푸스 문제는 ‘삭제’가 핵심이 아니라,
삭제될 대상을 찾을 때까지 나머지를 뒤로 돌리는
‘회전(Rotation)’ 과정이 핵심이다.
그리고 그 회전을 가장 자연스럽게 구현하는 자료구조가 큐이다.

---

📌 개인 문제풀이 레포

📂 GitHub
https://github.com/zzmnxn/algorithm-study