BOJ 11866. 요세푸스 문제 0

문제

코드 1

#include <iostream>
#include <queue>

using namespace std;
int num[1001];
int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }
    int cnt = 1;
    cout << "<";
    while (!q.empty())
    {

        q.push(q.front());
        q.pop();
        cnt++;

        if (cnt == k)
        {
            cout << q.front();
            q.pop();
            if (!q.empty())
                cout << ", ";
            cnt = 1;
        }
    }
    cout << ">\n";

    return 0;
}

• Runtime Error..
• 이 방법으로 하면 하나하나 숫자를 세가며 탐색하기 때문에 오래걸린다.

코드 2

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

using namespace std;
int num[1001];
int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }
    int cnt = 1;
    cout << "<";
    while (!q.empty())
    {
        for (int i = 0; i < k - 1; i++)
        {
            q.push(q.front());
            q.pop();
        }
        cout << q.front();
        q.pop();

        if (!q.empty())
        {
            cout << ", ";
        }
    }
    cout << ">\n";

    return 0;
}

• 앞에 k-1 만큼의 요소를 뒤로 push하고 난 뒤의 맨 앞의 요소를 출력한다.

배열, 벡터로 문제 풀려고 했기도 했고, 큐가 생각나기 까지 시간 엄청 걸렸던 문제...😨