#1. 기본 추상 자료형 (CHAPTER 4)

4.7. 응용문제

4.7.1. 리스트 ADT 응용

생일 케이크에 n> 0개의 불 켜진 양초가 원형으로 빙 둘러 서 있다. 생일 축하 게임으로, 첫 번째 양초부터 시작하여 k> 0개의 양초를 건너 꽂혀 있는 양초의 불을 끄고 뽑아낸다. 그리고는 다음 양초로부터 시작하여 k개의 양초를 건너 꽂혀 있는 양초의 불을 끄고 뽑아낸다. 이렇게 촛불을 끄고 뽑아내는 것을 원을 시계방 향으로 돌면서 양초가 하나만 남을 때까지 계속한다(당연히 케이크 주위는 점점 어두워진다). 마지막 양초는 겉보기엔 모르지만 내부에 특수장치가 설치되어 있어서 불이 꺼짐 과 동시에 멋진 축하쇼를 펼치도록 되어 있다. 이 특수 양초는 워낙 고가품이라 정확한 위치에 딱 한 개만 사용하고 싶다. 첫 번째 양초의 위치, 그리고 n과 k를 미리 알 경우, 원래 양초들의 원형 배치에서 특수 양초의 위치를 어디로 해놓아야 마지막까지 남을지 알고 싶다. 모의실행을 통해 특수 양초의 위치를 나타내는 양의 정수를 반환하는 알고리 즘을 작성하라. 원형의 양초 리스트를 다음 두 가지 데이터구조로 각각 구현해야 한다. 따라서 알고리즘도 두 가지 버전으로 작성해야 한다.

A. 배열을 사용한 구현 

배열을 사용하여 양초들의 상태를 관리하는 방법입니다. 각 양초가 제거되었는지 여부를 표시하는 배열을 사용합니다. 매번 k개의 양초를 건너뛰면서 양초를 제거하고, 제거된 양초는 표시된 배열에서 관리됩니다.

1. 초기화: 양초를 배열에 저장하고, 각 양초가 제거되었는지 여부를 나타내는 배열을 초기화합니다.
2. 제거 과정: 매번 k개의 양초를 건너뛰고 그 위치에 있는 양초를 제거합니다.
3. 종료 조건: 양초가 하나만 남을 때까지 계속합니다.
4. 결과 반환: 마지막으로 남은 양초의 위치를 반환합니다.

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

int candle(int n, int k){
    int cnt = 3; //cnt가 0이되어야 해당 인덱스의 값을 0으로 바꿈
    int remaining = n;//1이 남아있는 개수. 1이되면 함수 종료 및 반환
    
    int *num = (int*)malloc(sizeof(int)*n+1); //n개의 배열 0~n-1 : 0~9
    for(int i=0;i<n;i++)num[i] = 1; //0~9까지 각 인덱스에 1을 저장 -> 양초를 뽑았을때 0으로 바꿈

    int now = 0; // 0 <= now <= n-1
    while(remaining > 1){
        while(num[now] == 0){now = (now+1)%n;}

        // printf("index[%d] 제거\n",now);
        num[now] = 0; remaining --;
        // now = (now+1)%n;
        // printf("now = %d\n",now);
        for(int i=0;i<k;i++){
            if(num[now] == 0) {
                // printf(">>num[now] == 0인 now = %d\n",now);
                i --;
                now = (now+1)%n;
            }
            else if(num[now] == 1) {
                // printf(">>num[now] == 1인 now =ㅌ %d\n",now);
                now = (now+1)%n;
            }
        }

    }
    // if(remaining == 1) 
    return now;
}

int main(){
    int n = 10;
    int k = 2;
    int remaining = candle(n,k);
    printf("%d",remaining);
}

B. 원형 연결 리스트를 사용한 구현 

원형 연결 리스트를 사용하여 양초들을 원형으로 배열합니다. 리스트에서 양초를 제거하면서 마지막 하나가 남을 때까지 계속 진행합니다.

1. 초기화: 양초를 원형 연결 리스트에 저장합니다.
2. 제거 과정: 연결 리스트에서 k개의 양초를 건너뛰고 해당 노드를 제거합니다.
3. 종료 조건: 리스트에 하나의 노드만 남을 때까지 계속합니다.
4. 결과 반환: 마지막으로 남은 양초의 위치를 반환합니다.

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

typedef int element;

typedef struct listType{
    struct listNode* head;
    int size;
}listType;

typedef struct listNode{
    struct listNode* next;
    element data;
}listNode;

void init(listType* L){
    L->head = (listNode*)malloc(sizeof(listNode));
    L->size = 0;
}

void add(listType* L,element e){
    listNode* new = (listNode*)malloc(sizeof(listNode));
    new->data = e;

    if(L->size == 0) L->head = new;
    else{
        new->next = L->head;
        // L->head->next = new;
        L->head= new;
        // listNode* tmp = L->head;
        // for(int i=0;i<L->size;i++) tmp= tmp->next;
        // tmp->next = new;
        // printf("[%d] ",new->data);
    }
    L->size ++;
}

void printL(listType* L){
    listNode* tmp = L->head;
    for(int i=0;i<L->size;i++) {
        printf("[%d] ",tmp->data);
        tmp= tmp->next;
    }printf("\n");
}

// element delete(listType* L){

// }

int candle(int n, int k){
    int remaining = n;
    listType list; init(&list);
    for(int i=0;i<n;i++) add(&list,n-i);
    printL(&list);

    listNode* tmp = list.head;
    for(int i=0;i<list.size-1;i++) tmp= tmp->next;
    tmp->next = list.head;


    listNode* node = list.head;
    while(remaining>1){
        // while(num[now] == 0){now = (now+1)%n;}

        while(node->data == 0) node = node->next;
        printf(">>delete [%d]\n",node->data);
        node->data = 0;
        remaining--;
        
        // if(remaining == 1){printf("<%d>",node->data);}
        // node = node->next;

        for(int i=0;i<k;i++){
            if(node->data == 0) {i--; node= node->next;}
            else {node= node->next;}
        }
    }
    while(node->data == 0) node = node->next;
    printf("<%d>",node->data);
    

}

int main(){
    int n = 10;
    int k = 3;
    // int remaining = 
    candle(n,k);
    // printf("%d",remaining);
}