[연결리스트 | 기본문제] 1158번 : 요세푸스 문제 (못 품)

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

1158번: 요세푸스 문제

---

#include <bits/stdc++.h>
using namespace std;

const int MX = 5005;
int dat[MX], pre[MX],nxt[MX];
int unused = 1;
int target;

void insert(int addr, int num) {
	dat[unused] = num;
	pre[unused] = addr;
	nxt[unused] = nxt[addr];
	if (nxt[addr] != -1) pre[nxt[addr]] = unused;
	nxt[addr] = unused;
	unused++;
}

void erase(int addr) {
	cout << addr << " " << '\n';
	nxt[pre[addr]] = nxt[addr];
	if (nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

void traversal()
{
	int cur = nxt[0];
	while (cur != -1) {
		cout << dat[cur];
		cur = nxt[cur];
	}
}

int find_next(int k)
{
	int num = k;
	if (k == 0) return nxt[num];
	else return nxt[find_next(k - 1)];
}

int main() {
	fill(nxt, nxt + MX, -1);
	fill(pre, pre + MX, -1);
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
	{
		if (i == n)
		{
			insert(i - 1, i);
			nxt[i - 1] = 1;
			pre[1] = i;
		}
		insert(i - 1, i);
	}
	target = k;
	for (int i = 0; i < n; i++)
	{
		erase(target);
		target = find_next(target);
	}
}

원형 리스트로 풀어보려했는데

k번째를 삭제하는 로직 세우기에서 gg침 

원형 리스트도 제대로 연결됐는지 모르겟다..