요세푸스 문제0(11866)

들어가는 말

n명의 사람들이 있을 때, k번째의 사람을 제거하는(?!) 문제이다.

코드 설명

일단 n과 k를 받은 후, 큐 q에다가 1부터 n까지의 숫자를 집어 넣는다. 다음에는 while도 큐가 비어있지 않을때까지 돌리면서 조건을 실행해준다. k번째를 제거해야 하는데, 문제는 큐에서는 index 기능이 없다는 것이다. 베열이라면 가능했을 텐데! 하지만, 큐를 배열로 구현하면 시간이 더 들 거 같았기에 그냥 큐를 썼다.
사실 index를 쓰지 않고 k번재를 지우는 건 생각보다 간단했다. i를 0부터 k-1번째까지 즉, k 앞의 숫자까지 반복하는데 먼저 앞의 숫자를 뒤에 넣어주고 지워주면 된다. 이렇게 되면 자동으로 지우고픈 k번째 숫자가 앞에 오게 된다. 세상에... 이걸 한 번에 생각해내는 사람들은 엄청난 거 같다. 나는 아무리 생각해봐도 index말고 떠오르지 않아서 검색해 봤는데. ㅎㅎ...
k번째 수가 앞에 오고 사이즈가 0이 아닐 경우 앞의 수를 출력하고 ", "를 출력해준다. 여기서 ", "은 문자열임을 주의하라. 처음에 난 문자로 넣어주었다가 이상한 값이 나왔다. 마지막으로 q의 값이 1이면 수가 하나 남았다는 것이므로 마지막 수를 출력하고 '>'을 출력해준다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main() {
	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();
		}
		if (q.size() != 1) {
			cout << q.front() << ", ";
			q.pop();
		}
		else {
			cout << q.front() << '>';
			q.pop();
		}
	}

}