[softeer] 소프티어(파이썬): 강의실 배정 ★★★

문제

Softeer

- 강의실에 최대한 많은 강의를 배정하는 문제이다.

- 배정된 강의는 서로 겹치지 않아야 한다.

- 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

- 강의 개수가 N일때 1 ≤ N ≤ 10^6 인 정수이다.

- 시작시간이 S, 종료시간이 F일때 1 ≤ S ＜ F ≤ 10^9를 만족한다.

알고리즘

- 강의 수를 입력받는다.

- 반복문을 통해 강의의 시작시간과 종료시간을 입력받는다. 이때, 힙큐를 통해 리스트에 넣는다.

- 리스트를 힙큐를 통해 시작시간과 종료시간을 꺼낸다.

- 꺼낸 값의 시작시간은 그전에 종료시간보다 크거나 같으면 카운터 해준다.

- 카운터 해준 값은 강의실을 배정한 값이기 때문에 카운트 값을 출력한다.

코드

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

for _ in range(n):
    s, f = map(int,sys.stdin.readline().split())

    # f 기준으로 (f, s)가 heap 리스트 안에 들어간다.
    heapq.heappush(heap, (f, s))

# 초기값
v = 0
# 강의 수
count = 0
# heap 리스트가 0이 될때까지 반복한다.
while heap:
    # 가장 작은 원소를 삭제후 f, s에 넣는다.
    f, s = heapq.heappop(heap)

    # 시작시간이 초기값(종료시간)보다 크거나 같으면 카운터해준다.
    # 다음 기준값은 종료시간으로 초기화해준다.
    if s >= v:
        count += 1
        v = f

print(count)

결과

위 코드에서 while문 위에 print(heap)을 작성하여 heap 리스트 안에 어떤 모양인지 확인해보면 다음 출력 화면과 같이 나온다.

<출력화면>

코드를 분석하게 되면 heapq를 통해 시작시간과 종료시간을 입력받는 동시에 정렬시키는 방법을 이용한 것이다. sort() 함수를 사용하여 정렬하는 방법도 있지만 sort() 함수를 사용하게 되면 시간 초과가 나는 것을 확인할 수 있다. sort() 함수의 시간 복잡도는 O(N Log N)이고 heqppush() 함수의 시간복잡도는 O(Log N)이기 때문에 시간 초과가 나지 않고 실행되는 것이다. 마지막으로 조건문을 통해 시작시간이 종료시간보다 크거나 같으면 강의 수를 카운트 해주었고 반복문이 끝난 후 강의 수를 확인하여 최대 강의 수를 출력하면 된다.

github

junjange/CodingTest