큐 - 백준 1186번 요세푸스 문제0

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

IDEA

옛날에 비슷한 문제를 풀었어서 기억이 생생하다. 원형 큐였나 그런 걸 사용하면 된다했는데 그런 건 모른다. 

그냥 오로지 큐로 풀었다.

순서를 세면서 내가 원하는 순서가 아니라면 pop한 후 push해서 뒤로 보내버리면 된다. 

 

1번부터 시작이기떄문에 count = 1로 설정해둔다. 

1. 내가 원하는 순서가 아닌 경우 

front값을 저장한 후 pop , push를 통해 뒤로 보내버린다. count번째 사람이기에 그 다음 사람을 위해 count를 하나 세준다. 

2. 내가 원하는 순서인 경우 

count == k일 때다. 이 때는 front 값을 다른 answer라는 벡터에 저장한 후, pop을 통해 빼버린다. 

이 사람이 빠지고 난 후 다시 1번째사람부터 시작해 k번째 사람을 찾아야하므로 count = 1로 다시 초기화해준다.

 

코드 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	queue<int>q;
	vector<int>answer;
	for (int i = 1; i <= n; i++) q.push(i);
	int count = 1;
	while (q.size() > 1) {
		if (count == k) {
			answer.push_back(q.front());
			q.pop();
			count = 1;
		}
		else {
			int num = q.front();
			q.pop();
			q.push(num);
			count++;
		}
	}
	printf("<");
	for (int i = 0; i < answer.size(); i++) printf("%d, ", answer[i]);
	printf("%d>", q.front());
}