문제: head가 헤더 노드가 없는 순환 연결리스트를 가리키고 있을 때, 각 노드에는 데이터 필드(num)와 포인터 필드(link)가 포함됩니다. 데이터 필드에는 정수가 저장되며, i번째 노드의 데이터 필드 값은 i입니다. 함수를 작성하여 순환 연결리스트를 사용하여 원숭이 왕을 선택하는 과정을 시뮬레이션하세요: 첫 번째 노드부터 시작하여 "카운트"를 반복하고, k의 배수에 해당하는 노드를 삭제합니다. 이 과정을 반복하여 연결리스트에 노드가 하나만 남을 때까지 진행하면, 남은 노드가 원숭이 왕이 됩니다.

구현 방법 및 요구사항:

다음과 같은 구조체를 선언합니다:

struct node {
    int number;
    struct node* next;
};

접근 방식:

1. 구조체 node 정의:

• 순환 연결리스트의 각 노드를 나타내며, 원숭이의 번호 number와 다음 노드를 가리키는 포인터 next를 포함합니다.

2. 순환 연결리스트 생성:

• create 함수를 사용하여 n개의 노드를 가진 순환 연결리스트를 생성합니다. 각 노드는 한 마리의 원숭이를 나타냅니다.
• 각 노드의 번호는 1부터 n까지이며, 마지막 노드의 next는 헤더 노드를 가리켜 순환 구조를 형성합니다.

3. 순환 연결리스트 출력:

• displayList 함수를 사용하여 순환 연결리스트의 내용을 출력하여 연결리스트의 정확성을 검증합니다.

4. 원숭이 왕 선택:

• selectKing 함수를 사용하여 원숭이가 탈락하는 로직을 구현합니다.
• 카운트 기준 k에 따라 순환 연결리스트를 반복 순회하며, 카운트가 k의 배수인 원숭이를 삭제합니다.
• 최종적으로 남은 원숭이의 번호를 출력하여 원숭이 왕을 결정합니다.

5. 메인 함수:

• 사용자 입력을 통해 원숭이의 수 n과 탈락 기준 k를 받습니다.
• create를 호출하여 순환 연결리스트를 생성하고 초기 상태를 출력합니다.
• selectKing을 호출하여 원숭이 왕을 선택하고 결과를 출력합니다.

코드:

#include <stdio.h>
#include <stdlib.h>

/* 구조체 선언 */
struct node {
    int number;
    struct node* next;
};

/* 순환 연결리스트 생성 */
struct node* create(int count) {
    int i = 1;
    struct node* head = NULL;
    struct node* current = NULL;
    struct node* previous = NULL;
    
    do {
        current = (struct node*)malloc(sizeof(struct node));
        if (current == NULL) {
            printf("메모리 할당 실패!");
            exit(0);
        }
        
        if (head == NULL) {
            head = current;
        } else {
            previous->next = current;
        }
        
        current->number = i;
        
        if (current->number > count) {
            previous->next = head;
            free(current);
            break;
        } else {
            previous = current;
            i++;
        }
    } while (1);
    
    return head;
}

/* 순환 연결리스트 출력 */
void displayList(struct node* head) {
    struct node* current = head;
    
    if (current == NULL) {
        printf("연결리스트가 비어 있습니다");
        return;
    }
    
    while (1) {
        printf("%4d", current->number);
        current = current->next;
        if (current->next == head) {
            printf("%4d", current->number);
            current = current->next;
            
            if (current->next == head) {
                printf("%4d", current->number);
                break;
            }
        }
    }
    printf("\n");
}

/* 원숭이 왕 선택 */
void selectKing(struct node* head, int step) {
    int count = 1;
    struct node* prev = head;
    
    while (prev->next != prev) {
        if (count % step == 0) {
            prev->next = prev->next->next;
            displayList(prev->next);
        }
        if (++count % step != 0) {
            prev = prev->next;
        }
    }
    
    printf("\n원숭이 왕은 번호 %d인 원숭이입니다!\n", prev->number);
}

int main() {
    struct node* head;
    int monkeyCount;  // 원숭이 수
    int eliminationStep;  // 탈락 단계
    
    printf("원숭이의 수를 입력하세요 (n > 0): ");
    scanf("%d", &monkeyCount);
    
    if (monkeyCount <= 0) {
        printf("잘못된 입력입니다!");
        exit(0);
    }
    
    head = create(monkeyCount);  // 순환 연결리스트 생성
    displayList(head);  // 초기 연결리스트 출력
    
    printf("탈락 단계(k)를 입력하세요: ");
    scanf("%d", &eliminationStep);
    
    selectKing(head, eliminationStep);  // 원숭이 왕 선택 함수 호출
    
    return 0;
}

• 이 프로그램은 연결리스트를 사용하여 원숭이들이 원을 그리는 상황을 시뮬레이션하며, 순환 연결리스트의 특성을 이용하여 원숭이 탈락 과정을 구현합니다.
• 노드를 구조체로 표현하여 각 원숭이의 정보를 효율적으로 관리합니다.
• 노드를 삭제할 때 이전 노드의 next 포인터를 조정하여 순환 연결리스트 구조를 유지해야 함에 주의해야 합니다.
• 프로그램은 연결리스트 생성과 원숭이 탈락 과정의 중간 단계를 출력하여 실행 과정을 더 명확하게 보여줍니다.