[백준] 1158번 요세푸스 문제

문제: 1158번: 요세푸스 문제

 

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    deque<int> deq;
    for (int i = 1; i <= n; i++)
        deq.push_back(i);

    // k 번째 사람을 반복적으로 제거해야함
    // k 번째 사람을 구하기 위해서 맨 앞에 있는 수를 맨 뒤로 붙이는 과정을 k-1 번 반복 해야함.
    cout << "<";
    while (deq.size() != 1) {
        for (int i = 0; i < k - 1; i++) {
            int tmp = deq.front();
            deq.push_back(tmp);
            deq.pop_front();
        }

        cout << deq.front() << ", ";
        deq.pop_front(); // 맨 앞 요소 빼기
    }
    cout << deq.front() << ">";


    return 0;
}

 

덱을 이용하면 쉽게 해결할 수 있는 문제였다. 원형큐에서 회전은 맨 앞에 있는 요소를 큐의 맨 뒤에 붙이는 것을 의미함을 앞으로도 잘 알고 있으면 될 것 같다.

 

작년에는 이 문제를 어떻게 풀어야 하는지 잘 모르겠어서 포기했는데 이번에 보니까 쉽게 풀려서 당황스러웠다. 확실히 자료구조 수업을 들어야지 본격적인 알고리즘 문제를 해결할 수 있는 것 같다. 한동안 복습겸 자료구조 문제 싹 밀어야할 것같다.

 

 

 

참고자료:

11866번: 요세푸스 문제 0

-> 얘는 1158 문제랑 똑같은 코드 제출했는데 맞았다. 왜 분리해놓은거지??

 

[백준] 요세푸스 문제

[백준] 요세푸스 문제

 

[Python] 요세푸스 문제 (백준 1158번 파이썬) — 우린 모두 모났으니, 둥글게 살자

[Python] 요세푸스 문제 (백준 1158번 파이썬)