[BOJ] 1158 요세푸스 문제 (C++)

1. 문제 링크

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

 

2. 문제 접근

- 문제를 이해하는 것은 어렵지 않다. 

- 처음에 모든 인원을 삽입해주고, 중간 삭제를 위해서 list 등을 이용한 처리가 적합하다.

 

3. 문제 풀이

- std::list를 이용해서 전체를 모두 넣어준다.

- list에 대한 iterator를 순환 시켜서 계속 돌린다. 

- 이후, k번째에 해당하는 경우 삭제하고, 아닌 경우 다음 사람으로 넘어간다. (iterator값 증가)

- 유의할 점은, 삭제된 이후 시점에 가리키는 요소나 다음 사람으로 넘어갈때 요소가 끝인 경우 처음으로 되돌린다.

 

4. 소스 코드(C++)

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

int main(void)
{
	int n, k;
	int cnt = 1;
	list <int> josephus;
	list <int>::iterator iter;

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		josephus.push_back(i);
	}

	iter = josephus.begin();
	while (!josephus.empty())
	{
		if (cnt == k) // k번째에 해당하는 경우
		{
			cnt = 1;
			if (josephus.size() == n)
			{
				cout << "<";
			}
			if (josephus.size() > 1) // 1개 이상인 경우 출력할 값이 더있음.
			{
				cout << *iter << ", ";
			}
			else
			{
				cout << *iter << ">";
			}
			iter = josephus.erase(iter);
			if (iter == josephus.end()) // 끝 도달한 경우 다시 맨 앞 이동
			{
				iter = josephus.begin();
			}
		}
		else
		{
			iter++;
			cnt++;
			if (iter == josephus.end()) // 끝 도달한 경우 다시 맨 앞 이동
			{
				iter = josephus.begin();
			}
		}
		
	}
}