[C++] 백준 1158번 : 요세푸스 문제

http://boj.kr/1158

1158번: 요세푸스 문제

이 문제는 3가지 방법으로 풀 수 있다.

1. 벡터(vector): 데이터를 동적으로 추가 및 제거해야 할 때 사용. 벡터는 배열과 유사하지만 크기가 동적으로 조절되므로, 크기가 자주 변경되는 경우에 유용하다.
2. 큐(queue): 선입선출(FIFO) 구조를 가져야 할 때 사용한다. 요세푸스 문제와 같이 순차적으로 처리해야 하는 경우나 BFS 알고리즘 등에서 큐가 유용하게 사용되는 자료구조다.
3. 배열(array): 정적인 크기의 배열을 사용할 때 유용합니다. 크기가 미리 알려진 경우나 고정된 크기의 메모리를 사용해야 하는 경우 적합하다

 

1. vector로 푸는 경우

// 요세푸스 문제
#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> arr1;

    for (int i = 1; i <= n; i++)
    {
        arr1.push_back(i);
    }

    int checker = 1;
    vector<int> result;
    while (arr1.size())
    {
        if (checker == k)
        {
            result.push_back(arr1.front());
            checker = 1;
        }
        else
        {
            int temp = arr1.front();
            arr1.push_back(temp);
            checker++;
        }
        arr1.erase(arr1.begin());
    }

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

시간 복잡도는 O(N^2) 이다.
벡터에서 원소를 하나씩 제거한 후에 출력을 위한 result 벡터에 추가하고 있다.
이 부분이 비효율적이다.

벡터에서 원소를 제거하고 새로운 원소를 추가하는 과정은 O(N) 만큼 소요되므로, 전체적으로는 O(N^2)의 시간 복잡도가 발생한다.

최적화를 위해서는 if-else 문을

index = (index + k - 1) % arr1.size(); // 다음에 처리할 요소의 인덱스 계산

를 활용해 단순화하면 될 것이다.

즉, 하나씩 요소를 세는 방식이 아니라, index를 통해 한방에 뽑아낼 거라는 것이다.

아래는 개선된 코드다.

#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> arr1;

    for (int i = 1; i <= n; i++)
    {
        arr1.push_back(i);
    }

    int checker = 1;
    vector<int> result;
    int index = 0; // 현재 처리 중인 큐의 인덱스
    while (!arr1.empty())
    {
        index = (index + k - 1) % arr1.size(); // 다음에 처리할 요소의 인덱스 계산
        result.push_back(arr1[index]);
        arr1.erase(arr1.begin() + index); // 처리한 요소를 큐에서 제거
    }

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

2. array로 푸는 경우

#include <iostream>
#include <vector>
using namespace std;

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

    int arr[n];
    fill_n(arr, n, 1);

    int turn = 0, cnt = 0;
    int chk = 0;

    while (cnt != n)
    {
        if (arr[turn % n])
        { // 출력한 적이 없다면
            if (chk == k)
            {
                int ele = (turn % n) ? (turn % n) : n; // 차례일 때
                cout << ele;                             // 출력
                arr[turn % n] = 0;
                chk = 1;
                cnt++;
                if (cnt < n)
                    cout << ", ";
            }
            else
            {
                chk++;
            }
        }
        turn++;
    }
    cout << ">";
}

이 코드도 문제가 요구하는 사항은 만족하지만, 최적화가 되어있지 않다.

문제점

1. 동적인 자료구조가 더 효율적이므로 벡터를 활용하는 것이 더 낫다.
2. turn변수를 사용해 순환을 표현하였는데, 이런 직접적인 계산을 나머지 연산자를 통해 구현하는 편이 낫다.
3. 배열은 0부터 시작하는데, ele변수로 표현하려고 하였으나 알아보기에 다소 까다롭다.

1번 이슈로 벡터 사용이 더 낫지만, 굳이 배열을 쓴다고 한다면 아래와 같이 2,3번 이슈를 개선한 코드를 참고하자.

#include <iostream>
#include <vector>
using namespace std;

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

    vector<int> arr(n, 1);

    int cnt = 0;

    cout << "<";
    int index = 0;
    while (cnt < n)
    {
        index = (index + k - 1) % n;
        if (arr[index] == 1)
        {
            cout << (index + 1); // 1부터 시작하는 인덱스를 출력
            arr[index] = 0;
            cnt++;

            if (cnt < n)
                cout << ", ";
        }
        index++;
    }
    cout << ">";
}

3. queue를 사용하는 경우

이 문제는 사실 큐를 활용하면 아주 간단하게 풀이할 수 있다.
(뭐.. 이런저런 방법을 생각해보는 건 좋으니까.. )

직관적이고 간단하다.

// 요세푸스 문제
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;

    queue<int> q;

    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }

    cout << "<";

    while (q.size() > 1)
    {
        for (int i = 1; i < k; i++)
        {
            int temp = q.front();
            q.pop();
            q.push(temp);
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << ">";
}

끗!

3개의 자료구조를 이용해 풀어보았다....
(힘들어)