(C++) BOJ/백준 1158 - 요세푸스 문제

문제 출처 : BOJ 1158 - 요세푸스 문제 www.acmicpc.net/problem/1158

 

 

C++에 있는 STL의 queue를 배운 기념으로, 과제로 풀어야 하는 예제를 풀어보았다.

 

1부터 N번까지 N명의 사람들이 원을 이루면서 앉아있고, K번째 사람을 순서대로 제거하는 문제이다.

 

최종 코드

#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 << '<';
	int i = 0;
	while (q.size() - 1) {
		if (++i % k == 0) {
			cout << q.front(); cout << ", ";
		}
		else q.push(q.front());
		q.pop();
	}
	cout << q.front() << '>' << '\n';
	return 0;
}

선언한 큐에 1부터 n까지의 숫자를 메소드인 push()로 저장을 하고,

큐에 1명만 남을 때까지 반복문에서 k번째 사람을 출력한다.

k번째가 아닌 사람은 다시 push()로 큐 마지막에 저장한다.

큐에 남아있는 마지막 사람은 ", "가 필요없으므로 while문이 끝난 후에 출력해준다.

 

이 문제도 앞서 풀었던 스택 문제처럼 C언어로 풀었을 때보다 훨씬 더 간단하게 풀 수 있었다.