[BaekJoon 11866][⚪4] 요세푸스 문제 0

❓ 문제

백준 11866 - “요세푸스 문제 0”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (queue)

- 알고리즘

• Data Structure, queue

- 설명

queue를 사용하는 풀이이다.

전형적인 '요세푸스' 문제로, 'queue'를 사용해서 풀면 간단하다.

좀 특이한 점은 출력으로, <, >, ,를 섞어서 잘 출력해야 하므로 vector에 결과를 저장해 놓고 간단한 분기로 출력하는 방식으로 구현했다.

queue 자체의 삽입, 삭제는 O(1)이므로 전체적인 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <queue>


using namespace std;

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

    int iK{}, iN{};
    cin >> iK >> iN;

    queue<int> qJosephus{};
    for(int i = 1; i <= iK; ++i)
    {
        qJosephus.push(i);
    }

    vector<int> vecResult{};
    vecResult.reserve(iK);

    // 큐가 빌 때까지 반복
    while(!qJosephus.empty())
    {
        // 앞을 빼서 뒤로 넣는 걸 (iN - 1)번 반복
        for(int i = 0; i < iN - 1; ++i)
        {
            qJosephus.push(qJosephus.front());
            qJosephus.pop();
        }

        // 결과 벡터에 앞 숫자 push_back
        vecResult.push_back(qJosephus.front());
        qJosephus.pop();
    }

    // 결과를 깔끔하게 출력하고 싶어서 vector 사용
    cout << '<';
    for(int i = 0; i < static_cast<int>(vecResult.size()); ++i)
    {
        if(i)
        {
            cout << ", ";
        }

        cout << vecResult[i];
    }
    cout << '>';

    return 0;
}

---

💭 후기

요세푸스 문제는 대부분 queue를 이용해서 풀면 되지만, 오히려 출력의 분기를 좀 더 깔끔하게 처리하는 데 신경을 썼다. 이럴 땐 vector에 결과값들을 모두 저장해 놓고 간단한 분기로 출력하는 방식이 좋은 것 같다.