[Algorithm] 카페 주문처리 시스템

손님이 주문한 음료를 우선순위에 맞춰서 저장하여 처리하는 문제 (보안상 링크 및 자세한 설명 생략)

• 커피 종류는 최대 50개, 서로 다른 난이도를 가짐

• 하루에 최대 10,000명 손님이 한 명당 최대 10개 주문 가능 (커피 종류 중복 가능)

• 손님 번호는 1 ~ 100,000

• 커피 별로 주문 처리 시 우선순위 : 손님 주문 中 가장 높은 난이도 + 주문시각 오름차순 (같으면 주문 시각 오름차순)

• 주문 최대 호출 1만, 커피 만듬 호출 10만, 취소 호출 1만, 수량 체크 1만

함수

• void init( ... ) : 음료 난이도 초기화
• void order( ... ) : 손님이 주문한 음료 전송 (시간 포함)
• int supply(int kind) : kind 음료에서 가장 우선순위 높은 것 제조 (해당 손님 음료 모두 제조되면 손님 id 리턴)
• int cancel(int id, int kind) : id손님의 kind 음료 하나 취소 (없는 경우 0 리턴)
• int ask(int id) : id 손님이 음료 몇개 남았는 지 리턴

문제 풀이

각 커피 종류마다 Heap을 만들어 우선순위 순으로 관리해줘야 한다.

커피 종류는 최대 50개고, 주문은 최대 10만개가 들어올 수 있으므로 2차원 배열로 만들어 관리해도 풀 수 있다. (50 * 10만 = 500만으로 메모리 충분)

우선순위로 관리해야 할 값은 난이도, 시간이므로 구조체는 아래와 같이 선언하면 된다.

#define MAXCALL 100000
#define MAX 50

struct NODE {
    int order;
    int time;
    int id;
};

NODE heap[MAX + 1][MAXCALL + 1];
int heap_size[MAX + 1];

order 순으로 정렬하는데, order가 같은 경우에는 time 순으로 정렬하면 되는 것이다.

힙 구현

void push(int kind, NODE p) {
    int target = heap_size[kind] + 1;

    while (target != 1 && (heap[kind][target/2].order > p.order ||
        (heap[kind][target / 2].order == p.order && heap[kind][target / 2].time > p.time))) {
        heap[kind][target] = heap[kind][target / 2];
        target /= 2;
    }

    heap[kind][target] = p;
    ++heap_size[kind];
}

NODE pop(int kind) {
    int parent = 1; int child = 2;
    NODE res = heap[kind][parent];
    NODE temp = heap[kind][heap_size[kind]];

    while (child < heap_size[kind]) {

        if (child + 1 < heap_size[kind] && (heap[kind][child].order > heap[kind][child + 1].order ||
            (heap[kind][child].order == heap[kind][child + 1].order && heap[kind][child].time > heap[kind][child + 1].time))) {
            ++child;
        }

        if (temp.order < heap[kind][child].order || (temp.order == heap[kind][child].order && temp.time <= heap[kind][child].time)) break;

        heap[kind][parent] = heap[kind][child];
        parent = child;
        child *= 2;
    }

    heap[kind][parent] = temp;
    --heap_size[kind];

    return res;
}

나중에 특정 손님의 음료를 삭제하는 함수가 호출되는데, 그때마다 힙에서 pop해주면서 해당 음료를 찾아 관리하는 건 매우 시간 낭비다. (우선순위로 관리되기 때문에, 최악의 경우 heap의 맨 마지막 값을 삭제하도록 들어오면 모든 데이터를 pop했다가 다시 push해야 하는 최악의 경우가 존재한다.)

따라서 개수만 미리 체크할 수 있는 int형 배열을 만들어서 pop()을 했을 때, 갖고 있는 개수가 다르면 삭제되었다고 판단하고 해당 데이터를 버리고, 한번 더 pop해주는 방식으로 진행한다.

int real[MAXCALL + 1][MAX + 1]; // 전역 개수
int count[MAXCALL + 1][MAX + 1]; // 삭제할 때 갱신되는 개수

즉, 삭제할 때는 count에서만 값을 줄여준다.

pop()을 했을 때, 해당 손님의 음료 종류 값으로 real 값과 count 값이 같지 않으면 해당 음료는 취소된 경우이므로 버려주면 된다.

개수 선언 시 MAX+1을 해주는 이유는, 마지막 50번째 배열에 총 개수를 저장하기 위함이다. 총 개수가 1개일 때 주문이 들어오면, 해당 손님의 마지막 주문이 완료되는 것을 알 수 있다.

주문, 제조, 취소, 조회

void order(int orderTime, int cnt, int kindList[], int bell_id) {
    register int i;
    // bell_id의 주문 들어옴

    // 최대 난이도 구하기
    int max = -1;
    int now = 0;
    for (i = 0; i < cnt; ++i) {
        now = level[kindList[i]];
        if (max < now) {
            max = now;
        }
    }

    for (i = 0; i < cnt; ++i) {
        now = kindList[i];
        push(now, {max + orderTime, orderTime, bell_id});
        real[bell_id][now]++;
        real[bell_id][50]++; // 총 개수
        count[bell_id][now]++;
        count[bell_id][50]++; // 총 개수
    }

}

int supply(int kind) {
    register NODE s;

    while (true) {
        s = pop(kind);
        if (count[s.id][kind] != real[s.id][kind]) {
            real[s.id][kind]--;
            real[s.id][50]--;
        }
        else {
            break;
        }
    }

    int bell_id = s.id;
    int cnt = count[bell_id][50];

    if (cnt == 1) { // 마지막 주문
        real[bell_id][kind]--;
        real[bell_id][50]--;
        count[bell_id][kind]--;
        count[bell_id][50]--;
        return bell_id;
    }
    else { // 아직 남음
        real[bell_id][kind]--;
        real[bell_id][50]--;
        count[bell_id][kind]--;
        count[bell_id][50]--;
        return 0;
    }
}

// 취소 가능할 때 뺀 것을 heap에서 pop할 때 알고 다시 한번 pop 해야함

int cancel(int bell_id, int kind) {
    int cnt = count[bell_id][kind];
    if (cnt >= 1) { // 취소 가능
        count[bell_id][kind]--;
        count[bell_id][50]--;
        return 1;
    }
    else { // 취소할 주문이 없음
        return 0;
    }
}

int ask(int bell_id) {
    return count[bell_id][50];
}