작심 큰일 챌린지 - 컵라면 (파이썬)

새로 배운 개념이나 기술:
스케줄링 최적화 문제: 제한된 시간 내에 최대한 많은 보상을 얻는 문제로 우선 순위 큐를 사용해 풀 수 있다.
우선 순위 큐는 최솟값 or 최댓값을 빠르게 꺼내야 할 때 사용하는 자료구조로 스케줄링(작업 우선순위 정렬) 문제나 이벤트 순서 처리하는(우선 순위가 있는) 문제에 자주 쓰인다.

이번 문제를 통해 정렬 + 힙 조합 문제의 구조를 이해할 수 있었고 시간제한이 있는 최대 이득 문제는 힙을 사용한 작은 값 제거 전략을 써야겠다고 생각했다.

어려웠던 점과 해결 방법:
마감일보다 많은 문제를 넣지 않도록 하는 방법을 큐 크기를 이용해서 푸는 점이 어려웠다.
마감일 기준으로 정렬한 후 일단 보상을 하나씩 큐에 넣다가 마감일보다 큐의 크기가 커진다면 큐의 맨 앞의 원소(가장 작은 값)를 제거하는 식으로 풀었다.

그리디 + 최소 힙을 이용한 스케줄링 최적화

import sys, heapq
input = sys.stdin.readline
def solution():
    n = int(input())
    info = [list(map(int, input().split())) for _ in range(n)]
    # 데드라인 안에서 받을 수 있는 최대 컵라면 수를 구하기
    # 데드라인 기준 오름차순 정렬
    info.sort()
    # print(info)
    q = []
    for deadline, ramen in info:
        heapq.heappush(q, ramen)
        # 데드라인보다 문제 수가 많으면 가장 작은 컵라면 제거
        if len(q) > deadline:
            heapq.heappop(q)
    print(sum(q))
solution()