Algorithm/Problems

99클럽 코테 스터디 19일차 TIL + 그리디

공부좀하시졍 2024. 11. 16. 10:05

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

 

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대

littlefoxdiary.tistory.com