[알고리즘] - BOJ #11000 강의실 배정

• 이번 문제는 BOJ #11000, 강의실 배정입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

1.(잘못된 접근 방식) N개의 수업을 종료시간을 기준으로 오름차순 정렬한 뒤, 종료시간이 가장 작은 수업을 우선 배치한 뒤 이후 시작 가능한 수업들 중 다시 종료시간이 가장 작은 수업을 배치하는 방식으로 알고리즘을 구현했습니다.

위의 테스트 케이스의 경우는 이러한 접근 방식으로 해결 가능하지만, 아래와 같은 반례가 존재했습니다.

8
1 8
9 16
3 7
8 10
10 14
5 6
6 11
11 12
---
answer : 3

이와 같은 케이스에 대해 1번의 접근 방식은 4를 출력하는 오류가 발생했습니다. 예컨대 종료시간을 기준으로 정렬했을 때는 5 6 - 6 11 - 11 12와 같은 효율적인 조합으로 강의실을 구성할 수 없게 되었습니다.

이러한 반례를 통해 살펴본 결과, 종료시간을 기준으로 하는 접근 방식은 하나의 강의실이 주어졌을 때 해당 강의실에 최대의 수업을 넣는 것은 가능하게 하지만, 모든 수업이 강의실에 할당 되어야 하는 해당 문제와 같은 상황에서는 최적의 해를 구하지 못했습니다.

2.결국 모든 수업이 최소의 강의실에 할당되기 위해서는, 시작시간을 기준으로 오름차순 정렬한 뒤, 시작 시간이 빠른 순서대로 우선적으로 배치해야 했습니다. 그렇게 되면 논리적으로 위의 반례에 대해서 올바른 출력을 낼 수 있게 됩니다.

시간 복잡도

그렇게 접근 방식을 바꾼 뒤, 쉽게 풀 수 있을 줄 알았지만 시간 복잡도의 늪에 사로 잡히고 말았습니다.. 기존의 구현했던 코드는 O(N^2)의 복잡도를 가지고 있었던 터라 200,000개의 N에 대해서 최악의 경우 400억회의 연산을 수행하게 되는 문제점이 있었습니다.

이 문제로 오랜 시간 고민했고, prioiry queue와 heapq 등을 활용해서 여러 시도를 해봤지만, 근본적으로 구현 과정에서 문제가 있었습니다.

기존의 코드에서는 강의실 리스트를 따로 만들었고, 수업들을 순회하며 그 안에서 강의실 리스트까지 순회하게 되어 O(N^2)의 복잡도를 갖게 되었습니다.

백준에 올라와 있는 여러 질문들 공부하며 간단하지만 시간복잡도를 획기적으로 낮춘 코드들을 배울 수 있었습니다. 해당 코드들을 보며 제 코드에 맞게 다시 구현해 본 코드는 다음과 같습니다.

for _ in range(size-1):

    cur_val = pq.get() # 현재 수업
    tg = class_num[0] # classroom에 있는 원소의 종료시간 중 가장 작은 것
    if(cur_val[0] >= tg):
        # 수업이 들어갔다면, 기존의 가장 작았던 종료시간을 pop하고 대신 현재 수업의 종료시간을 추가 (즉, 해당 강의실의 종료시간을 연장한 셈)
        heapq.heappop(class_num)
        heapq.heappush(class_num, cur_val[1])
    else:
        # 만약 들어가고자 하는 수업의 시작시간이 여러 classroom의 가장 작은 종료시간 보다 작다면, 무조건 새로운 강의실을 만들어야 함
        # pop하는 것 없이 새롭게 put (강의실 추가되는 셈)
        heapq.heappush(class_num, cur_val[1])

print(len(class_num))

여기서 pq는 수업들을 담고 있는 priorityqueue 객체이고, class_num은 강의실을 담은 heaqp 객체입니다. 이때, class_num 객체에는 각 강의실에서 가장 늦은 종료시간들을 담아둡니다. 즉, 강의실에 배치된 모든 수업들을 담아둘 필요 없이, 새로운 수업이 배치될 수 있는지만 파악할 수 있도록 종료시간만을 담아두는 것입니다.

class_num은 heapq로 구현되어 있기 때문에 자연스럽게 모든 강의실 중 가장 종료시간이 빠른 강의실의 수업과 비교하게 되고, 만약 현재 수업이 해당 강의실에 들어갈 수 있다면, 비교 대상이 되었던 수업의 종료시간을 pop한 뒤, 자신의 종료시간을 push하여 업데이트 해줍니다. 물론 이 과정도 자연스럽게 heapq를 이용해 정렬이 됩니다. 이를 통해 시간 복잡도를 O(N)으로 낮추면서도 정확한 구현을 할 수 있게 됩니다.

Lesson

사실 이 로직을 몇 번 보고서도 정확히 이해가 되지 않아 쉽사리 받아들여지지 않았지만, 여러번 곱씹어보니 앞서 언급한 해당 문제의 풀이 방식을 정확하고 간결하게 나타내고 있다는 생각이 들었습니다. 자료구조를 적시에 사용할 수 있도록 공부해야겠습니다.

종종 보면서 여러번 익혀야 될 것 같습니다. 도움을 주신 많은 능력자 분들께 감사한 마음을 전합니다..

문제 바로가기 👉BOJ #11000