https://www.acmicpc.net/problem/1374
import sys
import heapq
input = sys.stdin.readline
n = int(input())
ls = []
for _ in range(n):
c,s,e = map(int, input().split())
ls.append([c,s,e])
ls.sort(key=lambda x : (x[1])) # 시작시간 정렬
room = []
heapq.heappush(room, ls[0][2]) # 가장 처음 시작하는 강의의 끝나는시간
for i in range(1,n):
if ls[i][1] < room[0]: # 강의 시작하는 시간이 강의가 가장 빨리 끝나는 시간보다 빠르면
heapq.heappush(room,ls[i][2]) # 강의 끝나는시간을 heapq에 넣어 강의실 + 1
else: # 강의 시작하는 시간이 강의가 가장 빨리 끝나는 시간보다 느리면 > 그 강의실 이용
heapq.heappop(room) # 가장 빨리 끝나는 강의실 out > 그 강의실 이용
heapq.heappush(room, ls[i][2])
print(len(room))
- 강의가 시작하는 시간을 기준으로 정렬한다.
- list.sort() : sort함수는 기존 리스트 자체를 정렬시킨다.
- key 매개변수, lambda를 기준으로 정렬한다.
- 만약 시작시간이 같을 때 종료시간을 기준으로 정렬하고 싶다면 lambda x : (x[1],x[2]) 를 작성하면 된다.
- heapq 모듈을 사용해 강의가 가장 빨리 끝나는 시간을 파악할 수 있다.
- 강의시작시간으로 정렬된 리스트를 돌면서 강의시작시간 보다 heapq에 들어있는 강의종료시간이 가장 빠른 강의와 비교한다.
- 강의시작시간이 가장 빠른 종료시간보다 빠르다면 새로운 강의실을 추가해야한다.
- 강의시작시간이 가장 빠른 종료시간보다 느리다면 그 강의실을 이용하면 된다.
- 이때, 종료된 강의 정보를 빼고 (heappop) 새로운 강의 정보를 추가한다.(heappush)
힙 자료구조
- heapq 모듈을 사용한다.
- heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 한다.
- 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
- heapq.heappush(heap, item): item을 heap에 추가
- heapq.heappop(heap): heap에서 가장 작은 원소를 pop & return
- heap이 비어있는 경우 indexError가 호출된다.
- heapq.heappop(heap) 을 사용하면 heap에서 가장 작은 원소를 제거함과 동시에 가장 작은 원소를 return한다.
- 원소를 삭제하고 싶지 않다면 heap[0] 인덱싱을 통해 접근해야 한다.
- heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 O(n)
참고 url: https://littlefoxdiary.tistory.com/3
'Algorithm > Problems' 카테고리의 다른 글
99클럽 코테 스터디 21일차 TIL + 완전탐색 (1) | 2024.11.17 |
---|---|
99클럽 코테 스터디 20일차 TIL + 완전탐색 (0) | 2024.11.17 |
99클럽 코테 스터디 18일차 TIL + 그리디 (1) | 2024.11.14 |
99클럽 코테 스터디 17일차 TIL + 그리디 (2) | 2024.11.14 |
99클럽 코테 스터디 16일차 TIL + 그리디 (1) | 2024.11.13 |