[백준1158] 요세푸스 문제 (C++)

BOJ 바로가기

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
int main() {
	int n,k;
	cin >> n;
	cin >> k;
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		q.push(i);
	}
	cout << "<";
	for (int i = 0; i < n-1; i++) {
		for (int j = 0; j < k - 1; j++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front() << ", ";
		q.pop();
	}
	cout << q.front() << ">";
	return 0;
}

문제풀이

숫자가 7개이고 간격이 3이라고 가정하자.

1 2 3 4 5 6 7

2 3 4 5 6 7 1 (1 pop, push)

3 4 5 6 7 1 2 (2 pop, push)

4 5 6 7 1 2 (3 pop!) --> 3 프린트

5 6 7 1 2 4 (4 pop, push)

6 7 1 2 4 5 (5 pop, push)

1 2 4 5 (7 pop!) --> 7 프린트

...

이런식으로 간격-1번 pop, push를 반복해주고 마지막엔 push를 하지 않고 pop으로 그대로 내보내는 게 포인트이다. 앞으로 자료의 앞->뒤->앞을 번거롭게 반복하며 제거/추가해줘야 하는 문제가 있다면 큐를 떠올리는 게 좋겠다.