[백준/c++] 1158번 요세푸스 풀이(실버4)

 

문제

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

1158번: 요세푸스 문제

 

 

풀이

1부터 n의 연속된 자연수 배열을 원형큐 형태로 배치하였을 때 k번째 숫자를 계속 제거해야 하는 문제이다.

리스트에서 중간 숫자를 계속 삭제해야 하는 문제이기 때문에 c++의 list(linked list)를 사용하였다.

알고리즘은 매우 간단하게 짰다.  1부터 n의 리스트를 생성한 후, 리스트의 값이 전부 사라질 때까지 반복문을 돌려 k번째 반복일 때 iter가 가리키는 출력과 동시에 삭제했다.

 

코드

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

int main()
{
	int n, k, i=1;
	list<int> li;
	cin >> n >> k;


	for (int i = 1; i <= n; i++) {
		li.push_back(i);
	}

	list<int>::iterator iter = li.begin();

	cout << "<";
	while (li.size()>1) {
		if (i%k == 0) {
			cout << *iter << ", ";
			iter = li.erase(iter);
		}
		else
			iter++;

		if (iter == li.end())
			iter = li.begin();

		i++;
	}

	cout << *iter << ">";
	return 0;
}