백준 1158(요세푸스 문제) c++

문제

1158번: 요세푸스 문제

1번 부터 n번까지 사람이 둥글게 원을 이루며 앉아 있다고 가정합니다.

이때, k번째 사람을 제거하는데 제거 당하는 사람의 순서가 오세푸스 순열이 됩니다.

예를들어 n=7이고 k=3이면 1번 부터 7번까지의 사람을 k번째 제거하면 k=3이므로

남아있는 사람은 1, 2, 4, 5, 6, 7이 되고 제거된 3은 요세푸스 첫번째 원소로 들어갑니다. 

또 k번째 사람을 제거하면 1, 2, 4, 5, 7이 되고 제거된 6은 요세푸스 두번째 원소로 들어갑니다.

이렇게 사람이 없어질때 까지 반복한 요세푸스 순열을 구하면 됩니다.

---

int n, k;
	cin >> n >> k;
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}

먼저 n과 k를 받고 큐(queue)q를 선언하고 for문을 통해 1부터 n까지의 수를 큐안에 넣어줍니다.

사람이 원형으로 있기 때문에 큐의 성질을 이용할 것입니다.

	cout << "<";

 문제에서 요구하는 출력 방식이 <숫자, 숫자, 숫자, 숫자> 이렇게 되어있으므로 먼저 "<" 형식을 먼저 출력해줍니다.

while (!q.empty()) {
		for (int i = 0; i < k-1; i++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front();
		q.pop();
		if (q.empty())
			break;
		else
			cout << "," << ' ';
	}

while문을 사용해 큐가 다 비워질때까지 while문을 반복할 것입니다. 

사진에서 1번은 원래 있는 큐입니다. 이제 2번 부터 for 문으로 들어갑니다.

2번에서 q.push(q.front())를 통해 큐의 맨 앞부분을 맨뒤로 넣어줍니다. 

3번에서 q.pop()을 통해 맨앞에 있던 1이 삭제됩니다.

이를 k-1번 반복합니다.

제거하는 숫자를 맨앞에 위치시켜야 하기 때문입니다.

제거하게될 숫자 3은 요세푸스 순열의 첫번째 원소이므로 cout<<q.front(); 로 출력해줍니다.

그럼 3을 제거해야하기 때문에 q.pop()를 사용합니다

이를 큐가 비워질때 까지 반복하면 됩니다.

---

전체코드입니다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}
	cout << "<";
	while (!q.empty()) {
		for (int i = 0; i < k-1; i++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front();
		q.pop();
		if (q.empty())
			break;
		else
			cout << "," << ' ';
	}
	cout << ">";
	return 0;
}