[백준/c++] 1158번: 요세푸스 문제

 

 

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

1158번: 요세푸스 문제

 

큐를 사용해서 푸는 문제.

우선 큐는 front에서 pop 되는데 k번째 원소가 빠져야 하므로 어떻게 하면 좋을지 고민했다.

그런데 생각보다 쉽게 그냥 1번째 원소부터 k-1번째 원소를 pop 해서 뒤에 넣어주면 된다. 그러면 내가 제거하고 싶은 k번째 원소를 출력하고 pop 해서 제거해주면 된다!

 

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

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k;
    queue<int> q;
    cin >> n >> k;
    for(int i=1; i<=n; i++) q.push(i);
    
    cout << "<";
    while(q.size() - 1){
        for(int i=0; i<k-1; i++){
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << ">\n";
    return 0;
}