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

1. 문제

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

1158번: 요세푸스 문제

 

---

2. 문제풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

int n, k, cnt;
queue<int> q;
vector<int> ans;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	cnt = n;

	for (int i = 1; i <= n; i++)
		q.push(i);

	while (n--) {
		for (int i = 1; i < k; i++) {
			q.push(q.front());
			q.pop();
		}
		ans.push_back(q.front());
		q.pop();
	}
	cout << '<';
	for (int i = 0; i < cnt; i++) {
		if (i == cnt - 1)
			cout << ans[i];
		else cout << ans[i] << ',' << ' ';
	}
	cout << '>';
}

---

3. 문제 평가 및 해설

 

이 문제는 다양한 방법으로 풀 수 있다. 대표적으로 리스트, 큐가 있는데, 나는 리스트에 굉장히 취약하기 때문에 큐로 문제를 풀었다. (원형 리스트를 구현하는 것은 언제나 어렵다.. 바킹독님의 야매 연결리스트를 기회가 되면 암기해야겠다.)

 

큐로 구현하는 방법은 다음과 같다.

문제풀이

그림과 같은 과정을 N번 반복하면 된다.

 

순차적으로 큐를 쌓고 k번 만큼 pop해준다. 이때 pop 해준 원소들을 다시 push를 해줘야 한다.

 

그러면 큐 내의 출력 원소로 다가갈 수 있는데, 해당 원소를 pop해주고 정답 배열(벡터)에 넣어준다.