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

이 문제는 큐(Queue)를 활용하여 풀 수 있는 상황이다.

이를 인지하는 방법은 앞에서부터 k번째 숫자를 계속해서 지워나가는 것이므로, 앞에서부터 호출을 하는 자료형인 Queue임을 인지하면 된다. 추가적으로 k번째 숫자가 나올 때까지 원이므로 계속해서 앞에 있는 숫자가 뒤로 보내지는 상황이므로 k번쨰 숫자가 아닌 수들은 pop하고 push하여 뒤로 보내면 된다.

 

해당하는 알고리즘으로 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>

using namespace std;

int main(void){
    int n, k;
    cin >> n >> k;

    queue<int> circular_data;
    vector<int> result_data;
    for(int i = 0; i < n; i++){
        circular_data.push(i + 1);
    } // Setting circular_data

    // 1개 남을때까지 k를 기준으로 계속 pop하고 push해서 뒤로 보내는 작업을 반복

    while(circular_data.size() != 0){
        for(int i = 0; i < k - 1; i++){
            int temp = circular_data.front();
            circular_data.pop();
            circular_data.push(temp);
        }

        result_data.push_back(circular_data.front());
        circular_data.pop();
    }

    // 결과 출력

    cout << "<";

    for(int i = 0; i < n - 1; i++){
        cout << result_data[i] << ", ";
    }
    cout << result_data[n - 1] << ">\n";

    return 0;
}