[알고리즘 스터디] 3주차_큐_백준 11866

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
이제 순서대로 K번째 사람을 제거한다.
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

코드

#include <iostream>
using namespace std;

enum { eMaxCount = 1000001, };

class Queue
{
public:
    Queue()
        : muCount(0u)
        , muFront(0u)
        , muBack(0u)
    {
    }

    void Push(int _iData)
    {
        if (eMaxCount <= muCount)
        {
            cout << "Queue overflow!" << endl;
            return;
        }

        miarrData[muBack] = _iData;
        muBack = (muBack + 1) % eMaxCount; // Linear queue가 아니기 때문. Ring queue.
        ++muCount;
    }

    void PushBack(int _iData)
    {
        if (eMaxCount <= muCount)
        {
            cout << "Queue overflow!" << endl;
            return;
        }
        
        Push(_iData);
        Pop();
    }

    // 내가 추가
    int size()
    {
        return muCount;
    }
    //

    bool Empty(void)
    {
        return 0 == muCount ? true : false;
    }

    int Front(void)
    {
        if (true == Empty())
        {
            // cout << "Queue underflow!" << endl;
            return -1;
        }

        return miarrData[muFront];
    }

    int Back(void)
    {
        if (true == Empty())
        {
            // cout << "Queue underflow!" << endl;
            return -1;
        }

        return miarrData[muBack-1];
    }

    void Pop(void)
    {
        if (true == Empty())
        {
            // cout << "Queue underflow!" << endl;
            return;
        }

        muFront = (muFront + 1) % eMaxCount;
        --muCount;
    }

private:
    int miarrData[eMaxCount];
    unsigned int muCount;
    unsigned int muFront;
    unsigned int muBack;
};

void Recursive(Queue* _Queue, int _Num)
{
	for (int i = 0; i < _Num - 1; i++)
	{
		_Queue->Push(_Queue->Front());
		_Queue->Pop();
	}
	std::cout << _Queue->Front();
	if (_Queue->size() > 1)
	{
		std::cout << ", ";
		_Queue->Pop();
		Recursive(_Queue, _Num);
	}
	else
	{
		return;
	}
}

int main(void)
{
	int N = 0;
	int K = 0;
	Queue* NewQueue = new Queue();

	cin >> N >> K;

	for (int i = 1; i < N+1; i++)
	{
		NewQueue->Push(i);
	}

	std::cout << '<';
	Recursive(NewQueue, K);
	std::cout << '>';
}