1158(큐)

들어가는 말

숫자가 원을 이루고 있을 때 K번째 수를 출력하는 요세푸스 문제다. 처음에는 나머지를 이용해서 풀어야 하나 싶었다. 그러나 이 문제는 큐를 이용하면 훨씬 쉽게 풀 수 있었다. K번째 숫자는 K-1개의 숫자의 뒤에 있기 때문에 K-1개의 숫자를 뒤로 보내고 K번째 숫자를 앞으로 빼서 출력하면 됐다. 그리고 while문을 q의 사이즈 -1까지 돌려주는데, 그 이유는 맨 마지막 숫자의 오른쪽에는 띄어쓰기가 들어가지 않기 때문이다.

코드 설명

일단 총 몇개의 숫자가 필요한지 N, 몇 번째의 숫자를 뺄 건지 K를 입력한다. 그리고 queue를 선언한 후 1부터 N까지의 숫자를 queue에 넣는다.

q의 사이즈 -1까지 while문을 돌리는데, for문을 0부터 k-1까지 돌리면서 K번째 앞의 숫자들을 push한다. 그리고 해당 숫자르 pop해서 K번째 숫자가 맨 앞에 오도록 한다. for문이 끝나면 K번째 숫자가 맨 앞에 왔다는 의미이니 front를 출력하고 해당 숫자를 pop해주면 된다. while문이 끝나면 queue에 마지막으로 남은 숫자와 '>'를 출력해주면 된다.

코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main() {
	/*총 몇 개의 숫자를 넣어서 몇 번째 간격의 숫자를 뺄 건지 N과 K를 받는다.*/
	int N, K;
	cin >> N >> K;
	
	queue<int> q;

	/*1부터 N까지 q에 넣는다.*/
	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	cout << '<';

	/*q의 사이즈 -1까지 돌린다. 그 이유는 출력의 형식 때문이다. 맨 마지막 숫자는 띄어쓰기가 없어어야 하는데, q의 사이즈까지 돌리면
	 맨 뒤의 숫자도 띄어쓰기가 되서 그렇다. 물론 if를 쓰는 방법도 있겠지만, 굳이 그렇게 까지?
	 for문을 0부터 K-1까지 돌리면서 K번째 숫자가 앞에 오도록 한다. 그리고 K번째 앞의 숫자들은 뒤에다가 push해주고 pop을 해서
	 K번째 숫자가 front에 오도록 한다.
	 for문을 마치면 K번째 숫자가 맨 앞에 있을 테니 출력을 하고 pop을 해주면 된다.*/
	while (q.size()-1) {
		for (int i = 0; i < K - 1; i++) {
			q.push(q.front());
			q.pop();
		}
		cout << q.front() << ", ";
		q.pop();
	}
	/*맨 마지막에 남은 숫자를 출력하고 >를 출력해서 문제를 끝낸다.*/
	cout << q.front() << '>';
}