[Baekjoon] 11866 - 요세푸스 문제 0 (C++)

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

11866번: 요세푸스 문제 0

처음엔 문제 이해가 잘 안 갔는데 그냥 처음부터 K번째 사람을 제거하고 다시 그 위치에서 K번째 사람을 제거하고... 계속 반복만 하면 되는 것 같더라고요. 중간의 데이터를 제거해야 하는 상황이라 자료구조 중 하나인 연결 리스트(linked list)를 사용하면 될 것 같다는 생각이 들었습니다.

 

연결 리스트는 C++에서 STL로 제공하는 list를 사용했습니다. 데이터 제거와 연결 리스트의 끝으로 이동하면 다시 처음으로 되돌리는 부분은 반복자(iterator)를 이용해 쉽게 구현할 수 있었습니다.

#include <iostream>
#include <vector>
#include <list>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	list<int> josephus;
	list<int>::iterator it;
	vector<int> answer;

	int n, k;
	cin >> n >> k;

	// 연결 리스트 초기화
	for (int i = 1; i <= n; i++) {
		josephus.push_back(i);
	}

	it = josephus.begin();

	// 요세푸스 순열 생성
	while (!josephus.empty()) {
		for (int i = 0; i < k - 1; i++) {
			it++;

			// 맨 끝에 도달했으면 다시 처음으로 돌아감
			if (it == josephus.end()) {
				it = josephus.begin();
			}
		}

		answer.push_back(*it);
		it = josephus.erase(it);

		// 맨 끝에 도달했으면 다시 처음으로 돌아감
		if (it == josephus.end()) {
			it = josephus.begin();
		}
	}

	// 요세푸스 순열 출력
	cout << "<";
	for (int i = 0; i < n; i++) cout << answer[i] << (i < n - 1 ? ", " : "");
	cout << ">\n";

	return 0;
}