[python 백준 2109] 순회강연

📜 접근 방법

우선순위 큐 사용

1. 날짜를 기준으로 오름차순 정렬을 한다.
2. 최소 힙을 이용하여 금액을 기준으로 넣어준다.
3. 만약 방금 넣어준 날짜가 heap의 길이를 비교한다. (day가 기한이기에 그 기한보다 heap에 있는 길이가 크면 기간안에 할수없음!)
   1. 날짜가 heap의 길이보다 크면 pop (금액이 작은 값을 pop)
4. heap에 들어있는 금액을 전부 더한다.

❌ 실패 코드

import sys

n = int(sys.stdin.readline())
lecture = [list(map(int, sys.stdin.readline().split()))  for i in range(n)]

lecture.sort(key=lambda x: x[1])

deadline = lecture[n - 1][1]

i = n - 1
tmp = -1
res = 0

while deadline > 0:
        max_p = 0
        if deadline == tmp:
                deadline = lecture[i][1]
                i -= 1
                continue
        else:
                check = -1
                for j in range(len(lecture)):
                        if lecture[j][1] >= deadline:
                                if max_p < lecture[j][0]:
                                        max_p  = lecture[j][0]
                                        check = j
                        else:
                                continue
                res += max_p
                tmp = deadline
                del lecture[check]
                i -= 1
                if i > 0:
                        deadline = lecture[i][1]
                else:
                        break
print(res)

✅ 정답 코드

import sys
import heapq

n = int(sys.stdin.readline())
lecture = [list(map(int, sys.stdin.readline().split()))  for i in range(n)]

lecture.sort(key=lambda x: x[1])

heap = []

for pay, day in lecture:
    heapq.heappush(heap, pay)

    if day < len(heap):
        heapq.heappop(heap)
print(sum(heap))

💡알게 된점

알고리즘 활용을 잘 하자..!