[리스트] 1168. 요세푸스 문제 2

1. 문제 해결 전략

요세푸스 문제1과의 차이점은.. 리스트를 사용하면 시간초과가 난다는 것이다.

입력되는 데이터 수가 50만개 까지 가능하기 때문에 iterator를 다 도는 것이 아니라

index를 선언해서 다음 위치를 수식으로 만든후에 바로 해당 iterator을 옮겨준후 지워줘야 한다.

 

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

int main()
{
	int n, k;
	cin >> n;
	cin >> k;

	vector< int> l(n);
	vector<  int> v;

	for (int i = 0; i < n; i++)
	{
		l[i] = i + 1;
	}
	auto iter = l.begin();
	int index = 0;
	printf("<");
	while (!l.empty())
	{
		index = (k + index - 1) % l.size();
		v.push_back(l[index]);
		l.erase(l.begin() + index);
	}

	for (int i = 0; i < v.size() - 1; i++)
	{
		printf("%d, ", v[i]);
	}
	printf("%d>\n", v.back());
}

 

2. 걸린 시간

실패

 

3. 느낀점

어제 푼 문제도 기억을 못한 것도 문제이고, 시간초과도 예상을 못했다.

당연히 중간중간의 삭제가 일어날테니 리스트가 좋다고 생각했는데 ..

stl을 따로 책으로 공부하지 않아서 그런지 함수의 쓰임새는 그렇다쳐도 시간복잡도 관련해서는 거의 무지했다.

이건 바로바로 생각은 못할것같고.. 리스트쓰다 시간초과나면 바꿔 쓰는식으로 해야겠다.

 

4. 링크

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