[Baekjoon] 11866번: 요세푸스 문제 0

 

 

 

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

11866번: 요세푸스 문제 0

 

---

 

문제 해결 과정

착안

입력받은 $N$ 과 $K$ 의 값에 따라 큐(queue) 자료 구조를 사용해 요소를 하나씩 dequeue하고 반복문의 현재 루프가 $K$ 의 배수 번째에 해당하는 루프이면 숫자를 출력, 아니라면 다시 enqueue를 수행하여 문제를 해결하고자 했다.

 

구현

크기가 고정된 큐 자료 구조를 사용하며, enqueue 및 dequeue 연산을 반복적으로 수행하기 때문에 효율적인 메모리 활용을 위하여, 문제에 맞게 원형 큐(circular queue, 환형 큐) 자료 구조를 작성하고 문제를 해결해보았다.

 

원형 큐 자료 구조를 만들 때 주의점은 일반 큐 자료 구조에서와는 다르게 empty 상태와 full 상태를 구분하기 위해서 한 칸을 비워놓아야한다는 점이다. 이 점에 유의하고, Front와 Rear가 Capacity를 넘어서는 때마다 앞에서부터 다시 인덱스가 시작되기 때문에 나머지 연산(%)을 활용해보았다.

* enqueue, dequeue 등의 메서드를 구현할 때, 나머지 연산 외에 조건문으로 비교하여 처리하는 것도 가능함.

 

그런데 주어지는 숫자 $N$ 의 값이 비교적 크지 않아서인지 STL의 큐 자료 구조 클래스인 std::queue<> 클래스를 사용해서 문제를 해결하는 게 더 빠르다... (STL 활용한 코드는 생략)

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

class CQueue
{
public:
	CQueue(int N)
	{
		Numbers = new int[N + 1];
		Capacity = Rear = N;
		for (int i = 0; i < N + 1; i++)
			Numbers[i] = i;
	}

	~CQueue()
	{
		delete[] Numbers;
	}

	void Enqueue(int n)
	{
		if (IsFull())
			return;

		Rear = ++Rear % (Capacity + 1);
		Numbers[Rear] = n;
	}

	int Dequeue()
	{
		if (IsEmpty())
			return -1;

		Front = ++Front % (Capacity + 1);
		int temp = Numbers[Front];
		Numbers[Front] = 0;
		return temp;
	}

	bool IsFull() const
	{
		return Front == (Rear + 1) % (Capacity + 1);
	}

	bool IsEmpty() const
	{
		return Front == Rear;
	}

private:
	int* Numbers;
	int Capacity;
	int Front = 0;
	int Rear = 1;
};

int main()
{
	int N, K;
	cin >> N >> K;

	CQueue cq = CQueue(N);

	cout << "<";

	int i = 1;
	while (true)
	{
		int num = cq.Dequeue();
		if (i++ % K)
			cq.Enqueue(num);
		else
		{
			cout << num;
			if (cq.IsEmpty())
				break;

			cout << ", ";
		}
	}

	cout << ">";
	return 0;
}

 

실행 결과

위: std::queue<> 클래스 활용한 결과 / 아래: 원형 큐 자료 구조를 직접 작성하여 문제를 해결한 결과