백준 #1158 요세푸스 문제 c++

백준 1158번 요세푸스 문제이다. 

 

이 문제는 이해하기만 하면 원형큐를 활용해서 구현하는데는 크게 어렵지 않다.

 

7 3을 입력 받았다면

 

1 2 3 4 5 6 7 에서 항상 세번째 숫자를 제거하는 것이다.

 

원형큐이기 때문에 세번째 숫자인 3을 제거하면

 

다음에 오는 세번째 숫자는 4 5 6 7 1 2 중에서 6이 될것이고

 

6이 제거된 그 다음에는 

 

7 1 2 4 5 중에서는 2가 될것이다.

 

위의 과정을 큐가 빌때까지 진행하면 된다.

 

아래는 C++로 구현한 코드 전문이다.

 

#include <iostream>
#include <queue>

using namespace std;

queue<int> q;
queue<int> temp;
int main() {
    int n;
    int k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++) {
        q.push(i);
    }
    cout << '<';
    while(!q.empty()) {
        int num = k;
        while(1) {
            if(num == 1) {
                if(q.size() == 1) {
                    cout << q.front() << ">";
                    q.pop();
                    break;
                }
                else {
                    cout << q.front() << ", ";
                    q.pop();
                    break;
                }
            }
            else {
                temp.push(q.front());
                q.pop();
                q.push(temp.front());
                temp.pop();
            }
            num--;
        }
    }
    cout << "\n";
}

 

이 문제의 핵심풀이는 일반 큐를 원형큐로 어떻게 변형시킬것이냐 이다.

 

이 것은 다른 큐를 선언하면 쉽게 해결가능하다.