[Python] BOJ(백준) 11000번 - 강의실 배정

링크

https://www.acmicpc.net/problem/11000

난이도(solved.ac 참고)

골드5

풀이

회의실 배정과 비슷하지만 좀 다른 문제이다. 회의실 배정은 한 개의 회의실만 있는 상태에서 할 수 있는 회의의 최대값을 구하는 것이었던 반면에, 강의실 배정은 주어진 모든 강의를 할 수 있도록 하는 강의실 수의 최소값을 구하는 문제이다.

후술하겠지만 시간 초과가 떠서 애를 좀 먹었다. 힙을 써야겠다고 생각하여 

1. 우선 첫 번째 강의의 종료 시간을 heap에 넣은 다음에
2. 그 값과 다음 강의의 시작 시간을 비교해서
   1. 만약 다음 강의의 시작 시간이 더 이르다면, 결국 강의실이 하나가 더 필요하게 된다. 두 번째 강의를 시작하려고 보니 아직 첫 번째 강의가 끝나지 않아서 강의실을 새로 구해야 하기 때문이다.
   2. 반대로, 첫 번째 강의의 종료 시간이 더 이르다면, 이제 강의실을 사용할 수 있는 상태이다. 그러므로 heap에서 기존의 값을 빼낸 다음에(heap.heappop(classroom)), 두 번째 강의의 종료 시간을 heap에 넣는다(heap.heappush(classroom, total_list[i][1]))
3. 이러한 반복을 리스트 전체를 돌 때까지 반복한다.

 

 

이렇게 하면 문제를 해결할 수 있다. 여담으로, 이 문제를 풀면서 느낀 게 두 가지 정도가 있다.

1. in을 가능하면 쓰지 말자, 다른 방식으로 처리하자

for i in range(1, len(total_list)):
    if total_list[i][0] < classroom[0]:
        heapq.heappush(classroom, total_list[i][1])
    else:
        if total_list[i][0] in classroom:
            heapq.heappop(classroom)
            heapq.heappush(classroom, total_list[i][1])
        else:
            heapq.heappush(classroom, total_list[i][1])

처음에 제출했던 코드이다. 물론, 처음에 if문은 불필요했던 점은 인지하고 있다. 그렇지만, 어쨌든 답으로는 갈 수 있는 코드였다. 근데 시간 초과가 떴다. 내 코드에서는 시간 초과가 뜰 만한 어떠한 요소도 없다고 생각했기 때문에, 문제는 5행 if total_list[i][0] in classroom: 에 있었다고 확신할 수 있었다.

2. 비슷한 문제의 코드를 아무 생각 없이 그대로 가져오지 말자

이 포스팅을 하기 전, 비슷하지만 좀 더 쉬운 문제인 회의실 배정을 포스팅했을 때 썼던 lambda 코드를 그대로 가져왔었다. 그렇지만, 이 문제에서는 끝나는 시간 순서대로 정리할 필요는 없다. 오히려 시작하는 시간 순서대로 정리했을 때 훨씬 더 물 흐르듯 자연스럽게 문제를 풀 수 있다. (끝나는 시간 순서대로 정리했을 때 문제를 풀 수 있는지는 안풀어봐서 모르겠다.) 어쨌든, 비슷한 문제의 lambda 코드를 그대로 가져왔다는 점이 문제 해결에 더 오랜 시간이 소요되게끔 했던 요소들 중 하나라고 생각한다.