백준 11866/ 요세푸스 문제0

원형으로 0번째 ~ 마지막 원소가 모두 제거될 때까지 무한으로 즐겨야 한다.

만약 벡터를 사용해서 원형으로 둘러 앉은 것을 구현했다고 치자,
K번째 원소를 제거했다면 해당 원소는 건너뛰고 idx를 세어야 하므로 K번째 원소를 -1로 밀어버리고 스킵하는 부분을 넣어야 한다.

어쨌든 벡터는 원소 제거에 있어 비용이 n만큼 드므로 -1로 밀어야 한다. erase를 써도 무방할 테지만 웬만하면 하지 말자.
저렇게 하면 코드가 너저분해질 것이 뻔하다. 어차피 계속 순차탐색을 할 것이므로 원소 제거에 좋은 list를 사용한다.

알고리즘은 다음과 같다.

1. list에 사람을 넣는다.
2. 첫 번째 원소부터 탐색하며 K번째 사람이면 제거된 순서를 저장할 벡터에 저장하고 제거한다. 이후 cnt=1로 초기상태로  돌아간다. 이 부분을 자세히 설명하면, 1 2 3 4 5 .. 의 상황에서 K=3일때, 3을 제거하고 4의 iter를 e로 받는다. 그러면 cnt를 세는 상황에서는 처음 1을 셀 때와 같은 상황이므로 cnt = 1로 한다.
3. 만약 K번째 사람이 아니면 몇 번째 사람인지 세는 cnt를 1증가시키고, e++를 통해 다음 사람으로 넘어간다.
4. 만약 직전에 본 사람이 마지막 사람이고 e++을 통해서 end()에 도착했으면 다시 처음으로 돌아간다.

#include <bits/stdc++.h>

using namespace std;

int main() {

    int N, K;
    cin >> N >> K;

    list<int> circle;

    for (int i = 0; i < N; ++i) {
        circle.push_back(i + 1);
    }

    list<int>::iterator e = circle.begin();
    int cnt = 1;

    vector<int> ret;
    while (!circle.empty()) {
        if (cnt == K) {
            ret.push_back(*e);
            e= circle.erase(e);
            cnt = 1;
        }
        else {
            e++;
            cnt++;
        }
        if (e == circle.end()) e = circle.begin();
    }

    cout << "<";
    for (auto i = 0; i < ret.size(); ++i) {
        if (i != ret.size() - 1) {
            cout << ret[i] << ", ";
        }
        else {
            cout << ret[i];
        }
    }

    cout << ">";

    return 0;
}