https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net

난이도: 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); }