백준 11866번: 요세푸스 문제 0

 

 

 

 

 

 

 

 

 

원형 큐 문제다.

큐 STL이 없었다면 front 와 rear 포인터를 사용해서 풀었겠지만 난 C++로 풀기 때문에 그럴필욘 없었다.

또한 vector로도 풀수 있다.

 

 

 

1. Queue로 푼 코드

 

#include <iostream>
#include <string>
#include <stack>
#include <queue>
using namespace std;

int n ,k;


int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	queue<int> q;
	
	cin >> n >> k;

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

	cout << "<";

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

	return 0;
}

 

 

 

STL을 사용하지 않는 방법에 대한 공부는 필요하니 간단히만 알아봤다.

 

시작은 front와 rear 모두 [0]자리에서 시작한다.

[1]자리부터 push가 되기 시작하며, push가 될 때마다 rear는 가장최근 입력된 값을 가리켰다.

front는 큐가 다 찰 때까지 빈공간인 [0]자리를 가리켰다. 

자리가 다 차서 [0]자리에 push를 해야하면 [1]자리를 비우고 front는 [1]을가리킨다.

front는 항상 빈 공간을 가리킨다는 것이 포인트다.

 

rear가 front바로 뒤에까지 오면 큐가 다 찼다는 소리다.

따라서 큐가 다 찼는지 확인하는 식은 다음과 같다.

front == (rear+1)%QueueSize

 

 

 

 

 

 

참고한 포스팅이다.

https://mailmail.tistory.com/41

[자료구조] 원형 큐의 기능 및 구현

 

 

 

 

2. Vector로 푼 코드

 

 

 

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
   int n, m; // n : 총 사람의 수 , m : 사람이 제거될 순서
   int elimPerNum = 1; // 제거되는 사람의 번호 (출력할 것)
                  // -> m번째 사람을 제거하는 것이므로 시작점을 포함해야 하기 때문에 초기값을 1로 준다.
   int cnt = 0; // 제거된 사람들의 수 -> n
   cin >> n >> m;
   vector<int> *Per = new vector<int>[n + 1]; // 1-based array
   for (int i = 0; i <= n; i++)
   {
      Per->push_back(i); // Per = {0, 1, 2, ... , n}
   }

   cout << "<";
   while (cnt < n)
   {
      elimPerNum += m - 1;   // 시작점을 포함하여 m번째 사람을 제거하는 것이므로
                        //오른쪽으로 m-1칸 가는 셈이다.
      while (1)
      {
         if (elimPerNum > Per->size() - 1) // Per.size() = 사람이 제거된 후 남은 사람들의 수 + 1이므로
         {
            elimPerNum -= Per->size() - 1;
         }
         if (elimPerNum <= Per->size() - 1) break;
      }
      cout << Per->at(elimPerNum);
      Per->erase(Per->begin() + elimPerNum);
      cnt++;
      if (cnt < n) cout << ", ";
   }
   cout << ">";
}