본문 바로가기

코딩 테스트

백준 11866

요세푸스 문제

자료구조 공부 중인데 마침 원형 연결 리스트를 사용하여 풀만한 문제가 나와 간단하게 클래스 구현 후 풀었다.

출력에 <> 를 빼먹어서 몇십분동안 고민했다....

 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

struct Node
{
	Node* next;
	int data;
};

class CircleList
{
public:
	Node* tail;
	Node* cur;
	Node* before;

	int numData;

	CircleList()
	{
		tail = nullptr;
		cur = nullptr;
		before = nullptr;
		numData = 0;
	}
	~CircleList()
	{
		delete tail;
	}

	void LInsert(CircleList* list, int datas)
	{
		Node* newNode = new Node;
		newNode->data = datas;

		if (list->tail == nullptr)
		{
			list->tail = newNode;
			newNode->next = newNode;
		}
		else
		{
			newNode->next = tail->next;
			tail->next = newNode;
		}


		numData++;
	}

	void First(CircleList* list)
	{
		if (list->tail == nullptr)
		{
			return;
		}

		list->before = list->tail;
		list->cur = list->tail->next;
	}
	void Next(CircleList* list)
	{
		if (list->tail == nullptr)
		{
			return;
		}

		list->before = list->cur;
		list->cur = list->cur->next;
	}

	int Remove(CircleList* list)
	{
		Node* rpos = list->cur;
		int data = rpos->data;

		if (rpos == list->tail)
		{
			if(list->tail == list->tail->next)
			{
				list->tail = nullptr;
			}
			else
			{
				list->tail = list->before;
			}
		}

		list->before->next = list->cur->next;
		list->cur = list->before;
		numData--;
		return data;
	}


};

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	CircleList* card = new CircleList;

	int input;
	int k;
	cin >> input >> k;

	for (int i = input; i > 0; --i)
	{		
		card->LInsert(card, i);
	}

	vector<int> die;

	bool f = true;

	card->First(card);
	while (card->numData > 0)
	{
		if (f)
		{
			for (int i = 0; i < k - 1; ++i)
			{
				card->Next(card);
			}
			f = false;
		}
		else
		{
			for (int i = 0; i < k; ++i)
			{
				card->Next(card);
			}
		}
		

		die.push_back(card->Remove(card));

	}
	cout << "<";
	for (int i = 0; i < die.size(); ++i)
	{
		if (i == die.size() - 1)
		{
			cout << die[i] << '>';
			break;
		}
		cout << die[i] << ", ";
	}



	return 0;
}

'코딩 테스트' 카테고리의 다른 글

백준 10773  (0) 2023.07.06
백준 7568  (0) 2023.07.05
백준 1547  (0) 2023.07.04
백준 1267  (0) 2023.07.03
백준 2741  (0) 2023.07.02