<배열,연결리스트> 백준 1158번 요세푸스 문제

 

문제접근

 

 중간에 삽입삭제가 빈번하면 리스트가 좋을것같아서 리스트를 두개 만들어서 풀려고했다.

#include <iostream>
#include <list>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;

	list<int> numbers;
	list<int> yosepus;

	//1~N까지 리스트에 숫자 입력받기 
	for (int i = 1; i <= N; i++)
	{
		numbers.push_back(i);
	}

	auto it = numbers.begin();
	//리스트의 사이즈가 0일때까지 반복
	while (!numbers.empty())
	{
		for (int i = 1; i < K; i++)
		{
			it++;
			//이터레이터가 범위 초과하면 시작위치로 보냄
			if (it == numbers.end())
			{
				it = numbers.begin();
			}
		}
		//이터레이터가 가리키는게 k번째면 k번째 숫자 yosepus에 넣기
		yosepus.push_back(*it);
		//K번째 숫자  지우기 numbers.erase(it)
		it = numbers.erase(it);
		if (it == numbers.end())
		{
			it = numbers.begin();
		}
	}

	//yosepus 리스트 출력 <3, 6, 2, 7, 5, 1, 4>
	cout << "<";
	for (auto it = yosepus.begin(); it != yosepus.end(); it++)
	{
		cout << *it;
		if (next(it) != yosepus.end())
		{
			cout << ", ";
		}
	}
	cout << ">";
}

 

근데 풀면서도 이렇게 풀면 배열로 푸는게 낫지않나? 싶어서 배열로 풀다가 이상한점을 발견했다. 문제에서 원형큐라는 힌트를 줬는데 큐를 쓸 생각을 미처 못했다. 그래서 원형큐를 이용하는김에 앞뒤 삽입삭제가 빠른 덱과 출력 수열을 담을 벡터를 이용했다. 

 

#include <iostream>
#include <deque>
#include <vector>

using namespace std;
//원형큐니까 덱에 저장
//출력수열은 배열에 저장
int main()
{
	int N, K;
	cin >> N >> K;

	deque<int> numbers;
	vector<int> yosepus;

	for (int i = 1; i <= N; i++)
	{
		numbers.push_back(i);
	}

	while (!numbers.empty())
	{
		//K번째 원소 맨앞으로 가져오기
		for (int i = 1; i < K; i++)
		{
			//K번째 원소 뒤로 가져오기
			numbers.push_back(numbers.front());
			numbers.pop_front();
		}
		//K번째 원소 제거하고 요세푸스에 저장
		yosepus.push_back(numbers.front());
		numbers.pop_front();
	}

	cout << "<";
	for (auto i = 0; i < yosepus.size(); i++)
	{
		cout << yosepus[i];
		if (i != yosepus.size() - 1)
		{
			cout << ", ";
		}
	}
	cout << ">\n";
}