[백준/BOJ] 백준 1158번 : 요세푸스 문제

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

1158번: 요세푸스 문제

list를 사용하여 문제를 해결했다. 현재 사람을 기준으로 k-1번 다음으로 넘겨서 제거할 사람을 찾았다.

 

코드

#include <iostream>
#include <list>
#include <vector>
using namespace std;

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

	int n, k;
	list<int> people; //list를 사용해서 문제를 해결했다
	list<int>::iterator it;
	int delete_num = 0;
	vector<int> result;

	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		people.push_back(i);
	
	it = people.begin();

	while (delete_num != n)
	{
		//제거할 사람을 찾으러 현재 사람을 기준으로 k-1번 다음으로 넘긴다
		for (int i = 0; i < k - 1; i++)
		{
			it++;

			if (it == people.end()) //마지막 사람을 넘으면 처음 사람으로 돌아온다
				it = people.begin();
		}

		result.push_back(*it);
		it = people.erase(it); //erase는 제거한것의 다음것을 가르키는것을 반환한다
		delete_num++;

		if (it == people.end()) //마지막 사람을 넘으면 처음 사람으로 돌아온다
			it = people.begin();
	}

	cout << "<";
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i];

		if (i != result.size() - 1)
			cout << ", ";
	}
	cout << ">";

	return 0;
}