[백준] 11866 요세푸스 문제0 - 연결 리스트

[ 문제링크 ]

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

 

🚩 조건

1. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어짐
2. 순서대로 K번째 사람을 제거
3. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나감, 모든 사람이 제거될 때까지 반복
4. 제거되는 순서를 (N, K)-요세푸스 순열이라고 함, N과 K가 주어지면 (N, K)-요세푸스 순열을 구해라

 

 

🚩 접근

1 -> 큐 또는 연결리스트로 구현하자

연결리스트로 구현하기로 함

 

 

🚩 시행착오

iterator을 사용하면 항상 segfault가 난다..ㅠ

- iterator++, iterator-- 등은 가능하지만 iterator+2 등 숫자와 연산은 불가능하다

 

- list.push_back(n) : iterator가 다음 원소가 들어갈 위치를 가리키도록 함께 움직인다

- list.begin() : 맨 앞의 원소를 가리킨다

- list.end() : 맨 마지막의 다음 원소를 가리킨다

 

입력이 "7 3" 일 때 list와 iterator의 변화

 

 

💻 코드 (C++)

#include <iostream>
#include <list>
using namespace std;

list<int> l;
list<int>::iterator iter;
int cnt;
int main(){
    int N, K;
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        l.push_back(i);
    }
    
    iter = l.begin();
    cout<<"<";
    while(!l.empty()){
        for(int i=0;i<K;i++){
            if(iter==l.end()){
                iter = l.begin();
            }
            iter++;
        }
        
        if(cnt!=N-1){
            cout << *(--iter) << ", ";
        }else{
            cout << *(--iter) << ">";
            break;
        }
        iter = l.erase(iter);
        cnt++;
    }
}

 

+ STL queue를 이용한 구현

원형 큐를 어떻게 구현해야할지 감이 안 와서 연결 리스트로 구현했는데, 아래와 같이 pop한 원소를 맨 뒤로 넣으면 원형 큐를 구현할 수 있다.

- stack, queue에는 iterator가 없다

- vector, deque, set, map, list 등에만 iterator가 있다

 

- STL queue를 사용할 수 없고 queue를 직접 구현해야 한다면 배열 또는 연결 리스트로 구현할 수 있다

#include <iostream>
#include <queue>
using namespace std;

queue<int> q;
int cnt;
int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }

    cout << "<";
    while (!q.empty()) {
        for (int i = 0; i < K-1; i++) {
            int next = q.front();
            q.pop();
            q.push(next);
        }
        int next = q.front();
        if (cnt != N - 1)
            cout << next << ", ";
        else
            cout << next << ">";
        cnt++;
        q.pop();
    }
}