[백준 1158] - 요세푸스 문제(C++)

인프런 강의에서 큐에 대한 단원에서 요세푸스 문제를 풀어보라고 해서 해 보았습니다.

예전에 비슷한거 풀었던거 같은데 이거랑 다른 문제였나 보네요

https://www.acmicpc.net/problem/1158

문제 분석

요세푸스 문제를 대략적으로 표현하면 원형으로 배치 후 특정 순번을 반복해서 제거하는 문제입니다.

큐를 통해 푸는 경우 제거대상 - n번째 순번이라고 할 때

큐에 해당 순번 전까지 pop(), push() 연산으로 뒤에 다시 삽입하고

n번쨰 순번에서 출력 후 pop() 연산을 해서 제거하면 됩니다. 

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<int> q;
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }
    int cnt = 0;
    string res = "<";

    while (!q.empty())
    {
        if (cnt!= k-1)
        {
            int tmp = q.front();
            q.pop();
            q.push(tmp);
            cnt++;
        }
        else
        {
            res += to_string(q.front());
            q.pop();
            if (!q.empty())
            {
                res += ", ";
            }
            cnt = 0;
        }
    }
    res += ">";
    cout << res << "\n";
}

저는 출력을 string 에 담아서 했는데 그냥 바로 출력해도 무방합니다.