[Python 알고리즘] 백준 11000번 : 강의실 배정

문제

• 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
• 수강신청 대충한 게 찔리면, 선생님을 도와드리자!
• 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

입력

• 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
• 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

# Case 1
3
1 3
2 4
3 5

출력

• 강의실의 개수를 구해라

# Case 1
2

내가 제출한 풀이 - Heap에 대해 공부 후 품

import sys
import heapq

n = int(sys.stdin.readline().strip())
class_list = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

class_list.sort(key=lambda x: x[0])

heap = []
heapq.heappush(heap, class_list[0][1])
res = 1

for i in range(1, len(class_list)):
    if class_list[i][0] >= heap[0]:
        heapq.heappop(heap)
    else:
        res += 1

    heapq.heappush(heap, class_list[i][1])

print(res)

처음에는 중첩 for 문을 이용해 풀었는데 시간 초과가 떴다. 최대 10억이란 수를 O(n^2) 풀기에는 너무 많은 시간을 사용한 것이다. 그래서 정렬된 배열을 비교하는데 O(n^2)를 사용 안 하는 방법을 찾으니 우선순위 큐인 Heap이라는 것을 알게 되었다.

Tip

lambda

class_list.sort(key=lambda x: x[0])

 

lambda 식은 python에서 제공하는 강력한 기능 중 하나이다. 쉽게 말하면 익명 함수라고 보면 된다. python에서 함수를 정의하는 def를 사용하지 않고 lambda 키워드를 사용하여 익명 함수를 만들 수 있다.

 

lambda 특징

1. 일회성 함수
2. 일회성 함수이므로, 한 번 쓰고 없어져 메모리에도 효율적이고 시간절약
3. 코드 간결성
4. return을 따로 명시하지 않음
5. 하나의 표현식으로만 만들어짐

"""
    class_list
    [[1, 3], [2, 4], [3, 5]]
"""

 

입력 예시 1을 입력하게 되면 class_list의 구조는 이렇다.

sort의 key 인자 값은 무엇을 기준으로 정렬할지에 대한 인자 값이다.

 

그렇다면 lambda x: x[0]은 무슨 뜻으로 쓰였는가? 에 대해 의문을 갖게 된다.

그것은 x가 class_list[i]를 뜻한다고 보면 되고 x[0]는 class_list[i][0]라는 것이다. 즉, 강의 시작시간을 기준으로 오름차순으로 정렬했다고 보면 된다.

 

heap

이번 문제로 통해 heap을 통해 알게 되었다.

heap과 우선순위 큐에 대한 정의 및 개념은 "우선순위 큐와 Heap이란?" 글에다가 따로 정리를 해놨다.