요세푸스 문제
자료구조 공부 중인데 마침 원형 연결 리스트를 사용하여 풀만한 문제가 나와 간단하게 클래스 구현 후 풀었다.
출력에 <> 를 빼먹어서 몇십분동안 고민했다....
#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;
}