[BOJ/백준 1158][C++] 요세푸스 문제

문제

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

 

문제 내용

이 문제는 예전에 한 번 푼 적이 있었다. (https://gyong0117.tistory.com/5?category=1050636)

이번에는 queue를 이용해 문제를 풀고자 한다.

문제는 별로 어렵지 않다.

1~N번까지의 사람이 원을 이루며 앉아있고, 계속해서 K번째 사람을 지워나가면 된다.
문제는 이 지워지는 사람의 순서를 출력하면 된다.

 

문제 풀이

이 문제를 큐로 어떻게 푼다는 것일까?
생각보다 간단하다.

처음에 1~n을 담은 queue를 만든다.

이후, 앞에서부터 k-1명을 pop()하고 다시 뒤에 push()하면 된다.

그러면 이제 queue의 front()에는 우리가 제거해야 할 k번째 사람이 남게 되어있다.

이를 출력해주고, 그다음에 다시 k-1명을 pop(), push()하는 과정을 거치면 된다.

(마지막에 한번에 출력해주고 싶다면, 결과를 담을 queue를 하나 더 만들어서 저장해주어도 된다.)

 

코드

#include <iostream>
#include <queue>
using namespace std;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n,k;
	cin >> n>>k;
	
	queue<int>q;
	for (int i = 1; i <= n; i++)q.push(i);

	cout << "<";

	//문제 해결
	while (q.size() > 1) {
		for (int i = 1; i < k; i++) {
			int tmp = q.front();
			q.pop(); //앞에서 빼서
			q.push(tmp); //뒤에 다시 넣는다
		}
		cout << q.front() << ", ";
		q.pop();
	}
	cout << q.front() << ">\n";
}

 

문제 코드 설명

1) 문제 해결

출력 형식(중간에 컴마 출력) 때문에 while문에서 q.size()>1 일 때 돌아가도록 했다. 

반복문의 조건에서 q.size()의 값을 확인하고 있기 때문에, 그 안의 코드 중 pop(), front()를 사용할 때 따로 큐가 비어있는지 확인할 필요는 없었다.