백준 20301 - 반전요세푸스 (C++)

1, 2, [3], 4, 5, 6, 7 --> 3 제거
1, 2, [3], 4, 5, [6], 7 --> 6 제거(6이 제거된 다음 7이 첫번째가 됨)
1, [2], [3], 4, 5, [6], 7 --> 2 제거
1, [2], [3], 4, 5, [6], [7] --> 7 제거
1, [2], [3], 4, [5], [6], [7] --> 5 제거
[1], [2], [3], 4, [5], [6], [7] --> 1 제거
[1], [2], [3], [4], [5], [6], [7] --> 4 제거

이 문제에서는 방향을 바꿔가며 사람을 삭제해야 하기 때문에 양 끝에서 push, pop이 모두 가능한 deque를 사용해 풀었다.

순방향일 때는 앞에서 k-1명을 pop 하고 뒤에 push 하면 된다.
그럼 deque의 front에는 제거해야 할 k번째 사람이 남고 이를 출력해주면 된다.

역방향일 때는 뒤에서부터 k-1명을 pop 하고 앞에 push 해주면 된다.
deque의 back에는 우리가 제거하고자 하는 k번째 사람이 남는데 이를 출력해주면 된다.

사람 한 명을 제거할 때마다 cnt의 값을 늘려주고 cnt의 값이 M과 동일해지면 check를 false로 바꾸어 방향을 바꿔주었다.

코드

#include <iostream>
#include <deque>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, K, M;
    cin >> N >> K >> M;
    deque<int> dq;
    
    for(int i=0; i<N; i++){
        dq.push_back(i+1);
    }
    
    int cnt = 0;
    bool check = true;
    while(!dq.empty()){
        if(check){
            for(int i=0; i<K-1; i++){
                dq.push_back(dq.front());
                dq.pop_front();
            }
            cout << dq.front() << "\n";
            dq.pop_front();
        }else{
            for(int i=0; i<K-1; i++){
                dq.push_front(dq.back());
                dq.pop_back();
            }
            cout << dq.back() << "\n";
            dq.pop_back();
        }
        cnt++;
        if(cnt==M){
            check = false;
            cnt = 0;
        }
    }
}