요세푸스 문제 풀이 - 연결리스트로 원형 구조 구현하기

김지섭·2025년 6월 6일

백준

목록 보기

10/26

문제 이해하기

요세푸스 문제는 N명의 사람이 원 형태로 앉아있고, K번째 사람을 계속 제거해나가는 문제입니다. 마지막에 남는 사람이 누구인지, 또는 제거되는 순서를 구하는 것이 목표입니다.

예시: N=7, K=3인 경우
1. 1,2,3,4,5,6,7이 원형으로 앉아있음
2. 3번째인 3을 제거 → 4부터 다시 시작
3. 4,5,6을 센 후 6을 제거 → 7부터 다시 시작
4. 이런 식으로 계속...

핵심 아이디어

이 문제의 핵심은 원형 연결리스트를 구현하는 것입니다. 배열로 구현하면 중간 원소 제거 시 모든 뒤 원소들을 앞으로 당겨야 하지만, 연결리스트를 사용하면 O(1)에 제거할 수 있습니다.

처음 시도했던 방법 (실패)

void trav(){
    if(cnt > 0){
        cnt--;
        cur = nxt[cur];
        trav();
    }
}

재귀함수로 K번 이동하려고 했지만, 전역변수를 사용해서 코드가 복잡하고 이해하기 어려웠습니다.

깨달은 점들

1. K의 정확한 의미

처음에는 K를 잘못 이해했습니다.

K=3이면 현재 위치에서 3번째 사람을 제거
즉, 현재 위치에서 K-1번 이동한 후 제거

2. 재귀보다 반복문이 더 직관적

// 복잡한 재귀 대신
for(int j = 0; j < k - 1; j++){
    cur = nxt[cur];
}

단순한 for문이 훨씬 이해하기 쉽고 디버깅도 편합니다.

최종 해결 코드

#include <bits/stdc++.h>
using namespace std;

int pre[100001];
int nxt[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    // 원형 연결리스트 구성 (1부터 n까지)
    for(int i = 1; i <= n; i++){
        if(i == 1)
            pre[i] = n;  // 첫 번째 원소의 이전은 마지막 원소
        else
            pre[i] = i - 1;

        if(i == n)
            nxt[i] = 1;  // 마지막 원소의 다음은 첫 번째 원소
        else
            nxt[i] = i + 1;
    }

    int cur = 1;  // 1번부터 시작
    cout << "<";
    
    for(int i = 0; i < n; i++){
        // K-1번 이동하여 K번째 사람으로 이동
        for(int j = 0; j < k - 1; j++){
            cur = nxt[cur];
        }

        // 출력
        if(i == n - 1)
            cout << cur << ">";
        else
            cout << cur << ", ";
            
        // 현재 원소를 연결리스트에서 제거
        nxt[pre[cur]] = nxt[cur];  // 이전 원소가 다음 원소를 가리키도록
        pre[nxt[cur]] = pre[cur];  // 다음 원소가 이전 원소를 가리키도록
        
        // 제거된 원소의 다음 원소로 이동
        cur = nxt[cur];
    }

    return 0;
}

알고리즘 분석

시간 복잡도: O(N×K)

N명을 제거하는데, 각 제거마다 최대 K번 이동
연결리스트 제거 자체는 O(1)

공간 복잡도: O(N)

pre, nxt 배열 각각 N개씩

다른 해결 방법 - STL 활용

연결리스트 구현이 복잡하다면 STL의 queue를 활용할 수도 있습니다:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    
    queue<int> q;
    for(int i = 1; i <= n; i++){
        q.push(i);
    }
    
    cout << "<";
    for(int i = 0; i < n; i++){
        // K-1번 회전
        for(int j = 0; j < k - 1; j++){
            q.push(q.front());
            q.pop();
        }
        
        if(i == n - 1)
            cout << q.front() << ">";
        else
            cout << q.front() << ", ";
            
        q.pop();
    }
    
    return 0;
}