BOJ - 조세퍼스 문제(1158)

이중 연결 리스트(Double Linked List)를 연습하기 위해 풀어본 문제입니다. 문제를 풀기 위해서 원형 링크드 리스트(Circular Liked List)를 구현해야 하는데 이중 연결 리스트를 이용해서 구현했습니다.

구조체 배열

struct Node {
	Node* next;
	Node* prev;
	int data;
}narr[5005];

int nidx = 0;
Node* allocNode() {
	return &narr[nidx++];
}

원형 링크드 리스트

Node* head = NULL;
Node* tail = NULL;

void addNode(int data) {
	Node* nn = allocNode();
	nn->data = data;
	if (head == NULL) {
		head = nn;
		tail = nn;
		nn->prev = tail;
		nn->next = head;
	} else {
		head->prev = nn;
		tail->next = nn;
		nn->prev = tail;
		nn->next = head;
		tail = nn;
	}
}

int delNode(int idx) {
	Node* cn = head;
	if (head == NULL) return 0;
	while (--idx) {
		cn = cn->next;
	}
	head = cn->next;

	cn->prev->next = cn->next;
	cn->next->prev = cn->prev;
	return cn->data;
}

메인 함수

#include <stdio.h>

int main() {
	int N, M;
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++) {
		addNode(i);
	}

	printf("<");
	for (int i = 1; i < N; i++) {
		printf("%d, ", delNode(M));
	}
	printf("%d", delNode(M));
	printf(">");
}