백준 1374 강의실 파이썬 (damn pythonic)

전형적인 그리디 알고리즘이다

1374번: 강의실

 

⭐️ 풀이

다른 분들 풀이 보니까 heapq 를 사용했던데, 나는 리스트를 사용했다.

 

1. 가장 먼저 시작하는 강의 기준으로 정렬 친다.

2. 차례대로 리스트에 저장하되, 끝나는 시간만 저장한다.

3. 강의를 차례로 순회 -> 리스트에 저장된 수보다 강의 시작 시간이 더 크다면, 저장된 인덱스에 끝나는 시간을 저장한다.

(이전 강의 끝나는 시간 < 다음 강의 시작시간 : 강의실 사용 가능)

 

강의실 교체가 필요할 때 del 이나 remove 를 칠까 생각도 했는데, 해당 인덱스의 값만 바꿔주면 더 간단히 풀 수 있다.

 

🌿 기존 코드

N = int(input())
temp = []
result = []

for _ in range(N):
    a, b, c = map(int, input().split())
    temp.append([b, c])
temp.sort(key=lambda x: x[0])
flag = True

for t in temp:
    start, end = t
    if len(result) == 0:
        result.append(end)
        continue
    for idx, r in enumerate(result):
        if r <= start:
            result[idx] = end
            flag = False
            break
    if flag:
        result.append(end)
    flag = True
print(len(result))

 

 

⚡️ 개선된 코드

파이썬 진짜 신태틱 슈가 쩐당 ㅋ

flag 로 괜히 분기 치지않고 for~else 사용했다. 개꾸르

N = int(input())

times = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
result = [times[0][2]]

for i, start, end in times[1:]:
    for idx, r in enumerate(result):
        if r <= start:
            result[idx] = end
            break
    else:
        result.append(end)

print(len(result))

 

 

➕ Heapq 를 사용한 풀이

import heapq

N = int(input())
times = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
min_heap = []
count = 0
for i, start, end in times:
    while min_heap and min_heap[0] <= start:
        heapq.heappop(min_heap)
    heapq.heappush(min_heap, end)
    count = max(count, len(min_heap))

print(count)

heapq 를 사용한 풀이가 월등히 빠른 것을 확인할 수 있다.

list 를 사용할 땐 for 문이 break 되지 않는 이상 result 를 모두 순회해야 한다. 따라서 heapq 에 비해 시간이 많이 소요될 수 밖에 없다.