[백준] 11866/1158 요세푸스 문제

1. 문제

두 문제는 모두 요세푸스 순열을 구하는 문제이다.
요세푸스 순열이란 N명의 사람이 원 형태로 앉아있을 때 K번째 사람을 제거하는데
N명의 사람이 모두 제거되는 순서를 말한다.

2. 풀이

우선 생각해야 할 것이 두 가지였다.
단순 벡터로 연산을 해서 구할 것인지, 혹은 다른 자료구조를 사용할 것인지.
하나는 K 이하의 사람이 남았을 때에는 어떤 순서로 제거할 것인지였다.

첫 번째 고민했던 것부터 보면 벡터를 사용해서 해당 인덱스의 요소를 제거해도
인덱스는 남아 있기 때문에 좀 불편할 듯 싶었다.
그래서 큐를 사용하여 K-1번 만큼 앞의 요소를 뒤에 다시 넣고
k번째 요소를 pop하는 방법을 사용했다.

두 번째 생각할 것은 K 이하의 사람이 남았을 때 이다.
K이하가 남았을 때 어떤 순서로 제거해야 하는지 헷갈렸던 것 같다.
하지만 문제를 잘 읽어보자. "원"의 형태로 앉아있다.
K 이하가 남았더라도 K-1번 만큼 순서를 돌 수 있다는 말이다.
따라서 같은 방법으로 큐가 빌 때 까지 pop하도록 했다.

3. 코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    queue<int> q;
    vector<int> num;
    for (int i = 0; i < n; i++) {
        q.push(i+1);
    }
    while (!q.empty()) {
        for (int i = 0; i < k-1; i++) {
            q.push(q.front());
            q.pop();
        }
        num.push_back(q.front());
        q.pop();
    }
    cout << "<";
    for (int i = 0; i < n; i++) {
        cout << num[i];
        if (i+1 == num.size())
            break;
        else
            cout << ", ";
    }
    cout << ">";
    return 0;
}