[자료구조] max heap 응용

오랜만에 과제 글이다.

사실 과제가 중간에 있었는데 귀찮아서 안 썼다. 

소프트웨어 프로젝트 과제를 여기 올리기에는 아직 안 끝나서... 자료구조만 올려보겠다. 

누군가 이 글을 보고 있기는 한 지 모르겠지만, 난 코딩을 잘 못하므로 피드백을 환영합니다. 뭐든 더 효율적인 코딩은 있기 마련이니까요.

 

과제 제출일은 5/29이다. (지연 제출일까지 포함한 날짜이다.) 이후 공개로 전환할 예정이다. 

사실 나도 오늘 한 거라 좀 양심이 없는 것 같기도 하고.

 

문제는 다음과 같다. 

 

어떤 식당에 식탁 크기가 2인용과 4인용 두 종류가 있다고 하자. 고객으로는 개인고객과 단체고객 두 유
형이 있다. 고객은 개인 (즉, 1명) 또는 단체 (2명 또는 3명 또는 4명까지로 한정)로 와서 인원수가 충분
한 식탁이 빌 때까지 대기한다. (예1: 3명 단체고객은 2인용 식탁에 앉을 수 없다. 그러나 4인용 식탁에
는 앉을 수 있다. 예2: 개인고객은 2인용 식탁에 앉을 수 있고, 4인용 식탁에도 앉을 수 있다.) 대기 고
객 간 합석은 제공하지 않는다.
개인 및 단체 고객은 식당 입구에서 식탁 대기번호표를 받는다. 도착 순서대로 9, 8, .... 번이 차례로 부
여된다. 식당의 당일 영업은 1번 고객의 식사를 마지막으로 종료하거나 또는 그 이전 임의의 번호 고객
의 식사를 마지막으로 종료할 수도 있다.
식당 카운터에서는 대기중인 고객별로 <대기번호, 인원수>의 대기 접수 데이터 레코드를 관리한다. 식탁
이 비면 그 식탁의 인원수보다 작거나 같은 인원수의 대기 고객 중 도착이 가장 먼저인 고객에게 배정한
다. 해당되는 고객이 없으면 식탁은 배정되지 않고 빈 채로 두었다가 향후에 배정을 시도하게 된다.
이상의 설명에 따라 식당카운터에서 고객 대기접수 및 빈 식탁의 배정을 수행하기 위한 프로그램을 아래
실행 예시를 참조하고 아래에 기술한 구현요건을 준수하여 작성하시오.

 

실행 예:
개인 및 단체 고객별 <대기번호, 인원수> 데이터가 도착순으로 <9, 3>, <8, 4>, <7, 1>, <6, 3>, <5, 2>
라고 할 때, 프로그램 실행화면의 예는 아래와 같다. 출력에서 ?: 로 표시된 곳에는 입력을 하고 엔터키
를 누른다. (예: 기능 선택?:, 인원수?:, 식탁 크기?:)

 

구현 요건:
1. 대기번호는 9에서 1까지 양의 정수 한자리 수로 한다.
2. “기능 선택?:” 에서 1번 대기접수가 입력되면 대기번호는 입력받지 않고, 9번부터 시작하여 다음 번
호가 자동으로 주어져서 화면에 출력되도록 한다, 인원수는 입력을 받아서 <대기번호, 인원수>의 데이터
레코드를 대기번호를 key로 하는 max heap에 push한다.
3. “기능 선택?:” 에서 2번 식탁배정이 입력되고, “식탁 크기?:” 에서 4인용은 4, 2인용은 2가 입력되면
식탁 크기에 관계없이 max heap의 루트에서 고객 데이터 레코드를 pop한다. 인원수 요건이 충족되면
배정을 완료한다. 그렇지 않으면 삭제된 고객의 데이터 레코드는 큐에 삽입하고, 그 다음 고객을 max
heap에서 pop하여 배정가능 여부를 판단하는 과정을 계속한다. 배정 가능한 고객이 있어서 배정 완료하
거나, 대기 중인 고객을 모두 max heap에서 pop하게 되면 (즉, 식탁 인원수 요건에 맞는 대기 고객이
없으면) 큐에 삽입된 고객 데이터를 차례로 삭제하여 max heap에 다시 push한다.

 

이번에는 문제가 좀 길다. 3번이 읽기 좋았는데... 그래도 어렵지는 않았다.

 

코드는 다음과 같다. 

 

#define MAX_NUM 10000
#define HEAP_FULL(n) (n == MAX_NUM - 1)
#define HEAP_EMPTY(n) (!n)
#include <stdio.h>
#include <stdlib.h>

typedef struct client* clientPointer;
typedef struct {
    int num;
    int peopleNum;
} client;

client assignment[MAX_NUM];
client queue[MAX_NUM];
int n = 0;
int front = -1, rear = -1;

void addq(client newClient) {
    rear = (rear + 1) % MAX_NUM;
    if ((rear + 1) % MAX_NUM == front) {
        fprintf(stderr, "The queue is full. \n");
        exit(EXIT_FAILURE);
    }
    queue[rear] = newClient;
}

client deleteq() {
    client temp;
    if (rear == front) {
        fprintf(stderr, "The queue is empty. \n");
        exit(EXIT_FAILURE);
    }
    front = (front + 1) % MAX_NUM;
    temp = queue[front];
    return temp;
    
}

void insertClients(client newClient, int* n) {
    int i;
    if (HEAP_FULL(*n)) {
        fprintf(stderr, "The heap is full. \n");
        exit(EXIT_FAILURE);
    }
    i = ++(*n);
    while ((i != 1) && (newClient.num) > assignment[i / 2].num) {
        assignment[i] = assignment[i / 2];
        i /= 2;
    }
    assignment[i] = newClient;
}

client popClients(int *n) {
    int parent, child;
    client waitingClient, temp;
    if (HEAP_EMPTY(*n)) {
        fprintf(stderr, "The heap is empty\n");
        exit(EXIT_FAILURE);
    }
    // 맨 위의 값 저장
    waitingClient = assignment[1];
    // 마지막 값
    temp = assignment[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n) {
        // 가장 큰 child
        if ((child < *n) && (assignment[child].num < assignment[child + 1].num)) child++;
        if (temp.num >= assignment[child].num) break;
        assignment[parent] = assignment[child];
        parent = child;
        child *= 2;
    }
    assignment[parent] = temp;
    return waitingClient;
}

int isAssignedPossible(int tableSize, client topClient) {
    if (topClient.peopleNum <= tableSize) return 1;
    else return 0;
}

int main()
{
    int input, waitingPeopleNum, totalNum = 9, tableSize, temp, assignPossible = 0
        , isEnd = 0;
    client newClient, nextClient, tempClient;
    printf("Start of Program\n");
    printf("기능\n");
    printf("0.종료 1.대기접수 2.식탁배정\n");
    printf("식탁 대기수: %d\n", n);
    printf("-------------\n");
    while (1) {
        printf("기능 선택?: ");
        scanf_s("%d", &input);
        if (input == 0) {
            printf("End of Program\n");
            break;
        }
        switch (input) {
        case 1:
            newClient.num = totalNum;
            printf("대기번호: %d\n", totalNum--);    // 
            printf("인원수?: ");
            scanf_s("%d", &waitingPeopleNum);
            newClient.peopleNum = waitingPeopleNum;
            insertClients(newClient, &n);
            printf("식탁 대기수: %d\n", n);
            printf("-------------\n");
            break;
        case 2:
            assignPossible = 0;
            printf("식탁 크기?: ");
            scanf_s("%d", &tableSize);
            temp = n;
            while (temp) {
                nextClient = popClients(&n);
                if (isAssignedPossible(tableSize, nextClient)) {
                    printf("배정:: 대기번호 : %d 인원수: %d\n", nextClient.num, nextClient.peopleNum);
                    assignPossible = 1;
                    break;
                }
                else {
                    addq(nextClient);
                }
                temp--;
            }
            while (rear != front) {
                tempClient = deleteq();
                insertClients(tempClient, &n);
            }
            front = -1, rear = -1;
            if (!assignPossible) {
                printf("배정불가::\n");
            }
            printf("식탁 대기수: %d\n", n);
            printf("-------------\n");
            break;
        }
    }
}

 

실행 결과는 다음과 같다.

 

 

구현 시간은 한 시간 정도...? 중간에 n이 0으로 나와서 왜 그러나 했더니 큐에서 다시 넣어주는 과정을 assignPossible을 검사하는 if 문 안에 넣어서 제대로 push가 이루어지지 않았던 거였다. 밖으로 빼주니 잘 작동했다. 

 

난 분명 코드 블럭 안에 쓰고 있는데, 왜 코드 블럭이 적용되지 않는걸까. -> 해결했다. 플러그인을 넣어주면 됐었음.

밋밋한 건 싫은데