[백준 / C언어] 1158번: 요세푸스 문제 (원형 연결 리스트 구현 / Circular Linked List)

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

1158번: 요세푸스 문제

난이도: solved.ac 실버 4

 

 

원형 연결 리스트 (Circular Linked List)를 이용해 구현해보자

 

일단 문제 이해가 어려울 수 있으니 문제에 주어진 예제 입력 1을 통해 이해해보자

 

아래 그림과 같이 먼저 3번이 제거된다

 

그리고 3번으로부터 3칸 떨어진 6번이 제거된다

 

그리고 이 3칸 떨어진 사람을 제거하는 과정을 모든 사람이 제거될 때까지 반복한다

 

 

 

우선 입력받은 N개 만큼 노드를 생성하고 원형 연결 리스트로 연결하는 과정을 구현하면 아래와 같다

 

void Insert(List* plist, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->head == NULL) {	// 큐가 비어있는 상황
		plist->head = newNode;
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
}

 

이를 그림으로 나타내면 아래와 같다

 

그리고 Shift라는 함수를 만들어서 삭제할 노드의 위치를 정해주었는데

 

cur은 삭제할 노드의 위치를 가리키고 before은 cur 바로 직전의 노드를 가리킨다

 

Shift를 실행하기 앞서 Cur_Init이라는 함수를 통해 cur과 before의 초기 위치를 tail로 지정해주었다

 

cur을 head에 두면 K만큼 이동했을 때 K+1번째 사람을 가리키기 때문이다

 

 

 

그 다음, cur이 삭제할 노드의 위치를 가리켰다면 Remove 함수를 통해 그 위치의 노드를 삭제시켜주었다

 

Remove 함수를 그림으로 표현하면 아래와 같다

 

[전체 코드]

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

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

typedef struct _List {
	Node* head;
	Node* tail;
	Node* cur;
	Node* before;
} CList;

typedef CList List;

void Init(List* plist);
void Insert(List* plist, int data);
void Cur_Init(List* plist);		// Shift를 하기 전 cur과 before가 tail을 가리키도록 초기화
int Shift(List* plist, int K);	// cur과 before을 이동시키는 함수
void Remove(List* plist);	// Shift 함수가 호출된 뒤 cur이 가리키는 node를 삭제

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

	List list;
	Init(&list);

	for (i = 1; i <= N; i++) {
		Insert(&list, i);
	}

	Cur_Init(&list);

	printf("<%d", Shift(&list, K));
	Remove(&list);

	for (i = 0; i < N - 1; i++) {
		printf(", %d", Shift(&list, K));
		Remove(&list);
	}
	printf(">");
	return 0;
}

void Init(List* plist) {
	plist->head = NULL;
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
}

void Insert(List* plist, int data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->head == NULL) {	// 큐가 비어있는 상황
		plist->head = newNode;
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
}

void Cur_Init(List* plist) {
	plist->cur = plist->tail;
	plist->before = plist->tail;
}

int Shift(List* plist, int K) {
	plist->cur = plist->cur->next;	// before과 한 칸 차이를 만들기 위해 cur을 따로 한 번 이동시킴
	for (int i = 0; i < K - 1; i++) {	// K > 1인 경우 cur과 before 이동
		plist->before = plist->cur;
		plist->cur = plist->cur->next;
	}
	return plist->cur->data;
}

void Remove(List* plist) {
	Node* rpos = plist->cur;
	if (rpos == plist->tail) {	// tail을 삭제하는 경우
		if (plist->tail == plist->tail->next) {	// 큐에 원소가 단 하나만 남았을 때 (사실 이 경우는 노드를 또 추가하지 않을 것이기 때문에 이 문제에선 불필요함)
			plist->head = NULL;
			plist->tail = NULL;
		}
		else
			plist->tail = plist->before;	// tail을 삭제하므로 tail의 위치를 옮겨줌
	}
	plist->before->next = plist->cur->next;
	plist->cur = plist->before;
	free(rpos);
}