C++ 자료구조 2 - 큐(queue)/백준 1158번

큐(Queue)는 뒤에서 자료를 넣고 앞에서 뺄 수 있는 자료구조이다. 대기줄을 생각해보면 된다.

놀이공원에 줄을 섰을 때 가장 먼저 줄을 선 사람이 기구를 먼저 타러 가고 늦게 온 사람들은 줄 서있는 사람들 뒤에 줄을 서지 바로 앞으로 가서 줄을 서면 안된다!! 큐가 이런 대기줄 개념이다.

먼저 넣은 것이 가장 먼저 나오기 떄문에 First In First Out(FIFO)라고도 한다.

 

queue의 method 들을 살펴보면

push : 큐에 자료를 넣는 연산

pop : 큐에서 자료를 뺴는 연산

front : 큐의 가장 앞에있는 자료를 보는 연산

back : 큐의 가장 뒤에있는 자료를 보는 연산

empty : 큐가 비어있는지 아닌지를 알아보는 연산

size : 큐에 저장되어있는 자료의 개수를 알아보는 연산

등이 있다.

 

1 2 3 4 5를 차례대로 큐에 넣었다고 생각해보자!

그냥 일반 대기줄을 생각하면 쉽다!

여기서 front()를 하면 맨 앞의 1이 리턴될 것이고 back()하면 맨 뒤의 5가 리턴될 것이다.

push(6)하면 5 뒤에 6이 들어갈 것이고 pop()하면 맨 앞의 1이 삭제된다.

그러면 큐에는 2 3 4 5 6 이 들어가 있을 것이다.

 

이 큐를 이용해서 문제를 풀어보자!!!!

백준 1158번 www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

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

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

 

풀어서 설명해보면

이렇게 1부터 N까지 원을 이루게 놓여있다고 생각을 해보자. 위에 문제에서 예시를 N을 7로, K는 3으로 들었기 때문에 나도 저렇게 가정하고 설명을 해보면

순서대로 K번째 사람을 제거한다는 뜻은

일단 먼저 K가 3이니까 1 2 3 4 5 6 7 중에 3번째인 3번을 제거한다.

그리고 4 5 6 해서 6이 제거되고 (3이 제거된 다음 수인 4에서 3개를 센다) 그다음에 7 1 2 해서 2가 제거되고 4 5 7 해서 7이 제거되고 1 4 5 해서 5가 제거되고 1 4 1 해서 1 제거, 그다음 4 4 4 해서 4가 제거되고 끝난다.

이것을 큐로 구현하면 front의 두 개를 뒤로 옮기고 세 번째는 pop 하는 걸 반복하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;

int main() {
	int n,m;
	scanf("%d %d", &n, &m);
	queue<int> q;
	queue<int> ans;
	for (int i = 1; i < n + 1; i++) {
		q.push(i);
	}
	printf("<");
	while (q.size()-1) {
		for (int i = 1; i < m; i++) {
			int t = q.front();
			q.pop();
			q.push(t);
		}
		printf("%d, ", q.front());
		q.pop(); //m번째 수 지우기
	}
	printf("%d>", q.front());
	q.pop();
	return 0;
}