[백준 11866] 요세푸스 문제 0 C언어

문제

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

11866번: 요세푸스 문제 0

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode { // 구조체 선언
	int k;
	struct ListNode* llink;
	struct ListNode* rlink;
}ListNode; // 이중 연결 리스트
int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);

	ListNode* l = (ListNode*)malloc(sizeof(ListNode)); // head 노드
	ListNode* before = NULL; // 이전 (유동성)

	l->k = 1;
	l->llink = NULL;
	l->rlink = NULL;
	before = l;
	for (int i = 2; i <= n; i++) {
		ListNode* new = (ListNode*)malloc(sizeof(ListNode)); // 새로운 노드에 공간 할당
		new->k = i;
		new->rlink = NULL;
		new->llink = before;

		before->rlink = new;
		before = new;
	}
	
	ListNode* temp = l;
	printf("<");
	while (l->rlink != NULL) {
		for (int i = 1; i < k; i++) {
			if (temp->rlink == NULL)
				temp = l;
			else
				temp = temp->rlink;
		}

		printf("%d, ", temp->k);
		if (temp->llink == NULL) { // 맨 앞 노드를 삭제해야 하는 경우
			ListNode* remove = temp;
			temp = temp->rlink;
			l = temp; // 헤드노드의 값도 변경해야 함
			temp->llink = NULL;
			free(remove);
		}
		else if (temp->rlink == NULL) { // 맨 뒤 노드를 삭제해야 하는 경우
			ListNode* remove = temp;
			temp->llink->rlink = NULL;
			temp = l;
			free(remove);
		}
		else {
			ListNode* remove = temp;
			temp->llink->rlink = temp->rlink;
			temp->rlink->llink = temp->llink;
			temp = temp->rlink;
			free(remove);
		}
	}
	printf("%d>", l->k);

	return 0;
}

주의할 점

typedef struct {...} ListNode; 에서 ListNode가 구조체의 별칭이므로 구조체 선언을 해줘야 한다. 

헤드 노드의 값도 변경해줄 필요가 있다.