[C++] 백준 11866번 : 요세푸스 문제 0 && queue에 대하여

- 큐(queue)

출처 : https://iq.opengenus.org/priority-queue-cpp-stl/

1. Def : 대기줄이라는 영어 뜻 그대로, 뒤에서 value가 추가되고, 앞에서 사라지는 구조이다. 가장 처음으로 넣은 값(First In)이 가장 처음으로 빠진다(First Out)는 의미에서, FIFO구조(First In First Out)라고 불린다.
2. Functions to use : push, pop, empty, front, back, size etc.
   • push(x) : 큐의 가장 윗 데이터에 메모리를 생성, 데이터 x를 넣는다.
   • pop() : 큐의 가장 처음에(오래 전에) 입력된 데이터를 삭제한다. 큐가 비었다면 연산 정의 불가상태(error 발생)가 된다.
   • empty() : 큐가 비었다면 1을 return하고, 그렇지 않다면 0을 반환한다.
   • front() : 큐의 가장 처음에(오래 전에) 입력된 데이터를 반환한다. 큐가 비었다면 연산 정의 불가상태(error 발생)가 된다. cf) stack의 경우, bottom()에 해당하는 함수인 것이다.
   • back() : 큐의 가장 마지막(최근에) 입력된 데이터(가장 처음 저장된 값)를 반환한다. cf) stack의 경우,top()에 해당하는 함수인 것이다.
   • size() : 큐의 길이를 return해준다. 큐가 비었다면 연산 정의 불가상태(error 발생)가 된다.
   • emplace(x) : push(x)와 결과적으론 같은 것을 수행하지만, 연산속도가 더 빠르다.
     push() : 입력받는 값의 복사본을 큐의 마지막에 저장.(복사본 생성 -> 큐에 저장)
     emplace() : 입력받는 값 자체를 큐의 마지막에 저장,(큐에 저장)
     누군가의 속도 측정 결과, int type에선 emplace가 유리했지만, 이 외에선 비슷했다고 한다.
   • a.swap(b) : a와 b라는 큐를 동적으로 바꿔준다. 주소까지 바뀐다.
3. How to make : pointer객체를 가지는 queue란 class를 만들고, 각각의 함수를 구현해주면 된다. 사실 다른 분들 거 코드를 봤는데 어려워서 STL을 사용했다. 조금 더 공부가 필요하다...
4. How to use :  이미 만들어져 있어서, 그냥 #include <queue> 이후에  queue<자료형> 변수명 형태로 만들면 된다.

//swap의 주소 변경 유무 확인실험//
#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;


int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL), cin.tie(NULL);
	queue<int> p,y_p;

	p.push(1), y_p.push(2);
	cout << p.front() << " " << &p.front()<<endl;
	cout << y_p.front() << " " << &y_p.front() << endl;

	p.swap(y_p);
	cout << p.front() << " " << &p.front() << endl;
	cout << y_p.front() << " " << &y_p.front() << endl;
    
    return 0;
}

//OUTPUT//
1 00825AF8
2 00825B38
2 00825B38
1 00825AF8

 

 

 

-Ref

https://stackoverflow.com/questions/35518611/difference-between-queues-emplace-and-push

Difference between <queue>'s emplace and push

https://iq.opengenus.org/priority-queue-cpp-stl/

Priority Queue in C++ STL

 

 

 

---

- 문제

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

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)

 

- 출력

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

 

- 예제 

//INPUT//
7 3

//OUTPUT//
<3, 6, 2, 7, 5, 1, 4>

 

 

---

- 구상

queue를 가지고 원과 같은 구조를 어떻게 만들까 생각하다가,

• 사라지지는 값은 pop()만으로 날리고,
• 사라지지 않는 값은 push를 통해 뒤로 보내고, pop()을 하면 되겠다는 생각이 들었다.

➡ 1부터 천천히 1씩 증가하는 i라는 변수를 설정하고, 입력받은 K를 나눴을 때의 나머지가 0인 순간의 값이 사라지는 구조를 설정하면, 즉, queue만 가지고 생각하지 않고 i를 따로 두고 생각하면, 범위를 벗어나며 생기는 error등을 해소할 수 있다.

 

 

 

---

- 구현

생각없이 길이에 따라 달라지게 만들었지만, 왼쪽 꺽쇠(<)를 먼저 출력하고 값들을 출력하는 방식을 사용하면 코드 길이를 줄일 수 있다!

p : 1~N까지 입력받는 queue.

y_p : 요세푸스 순열을 입력받는 queue.

#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;


int main() {

	ios_base::sync_with_stdio(false); cout.tie(NULL), cin.tie(NULL);
	
	// 1 2 3 4 5 6 7

	int K, N;
	cin >> N >> K;
	queue<int> p,y_p;

	for (int i = 1; i <= N; i++) {
		p.push(i);
	}
	int i = 1;
	while (y_p.size() != N) {
		if (i % K == 0) {
			y_p.push(p.front());
			p.pop();
			i++;
		}
		else {
			p.push(p.front());
			p.pop();
			i++;
		}
	}

	if (y_p.size() == 1) {
		cout << "<" << y_p.front() << ">";
	}
	else if (y_p.size() == 2) {
		cout << "<" << y_p.front() << ", " << y_p.back() << ">";
	}
	else {
		cout << "<" << y_p.front();
		y_p.pop();
		while (y_p.size() != 1) {
			cout << ", " << y_p.front();
			y_p.pop();
		}
		cout << ", " << y_p.back() << ">";
	}
	

	return 0;

}