[Silver 4] 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

 

이 문제는 큐를 사용해서 해결할 수 있다.

 

알고리즘은 다음과 같다.

• N명이 원을 이루며 앉아있고, K번째 사람을 제거해야한다.
• 이는 K번째 요소를 큐에서 제거하는 방식으로 해결할 수 있다.
• 즉, counter를 통해 K번째 pop 했는지 검사한다.
• K번 pop하지 않았다면 다시 큐의 뒤에 삽입한다.

#include <iostream>
#include<queue>
using namespace std;
int N, K;
int main() {
	cin >> N >> K;
	queue<int> q;
	vector<int> result;
	int counter = 1;
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}
	int check = 1;
	while (result.size()!=N) {
		int value = q.front();
		q.pop();
		if (check == K) {
			result.push_back(value);
			check = 0;
		}
		else {
			q.push(value);
		}
		check += 1; 
	}

	cout << "<";
	for (int i = 0; i < result.size() - 1; i++)
		cout << result[i] << ", ";
	cout << result[result.size() - 1] << ">" << '\n';
}