2/7 Coding Test

✅ Coding Test

🎈 1781 컵라면

문제 N개가 주어질 때 각 문제는 [데드라인, 컵라면 수]로 구성되어 있다. 즉 문제를 푸는 사람은 데드라인 내 문제를 풀면 컵라면 수만큼 컵라면을 얻을 수 있다.
최종적으로 주어진 데드라인 내 최대 얻을 수 있는 컵라면 개수를 구하는 문제

import sys, heapq
input = sys.stdin.readline

n = int(input())
ramen = []
for _ in range(n):
    ramen.append(list(map(int, input().split())))
ramen.sort(key=lambda x: x[0])

heap = []
for i in range(n):
    heapq.heappush(heap, ramen[i][1])
    if len(heap) > ramen[i][0]:
        heapq.heappop(heap)
print(sum(heap))

< 해설 >

우선순위 큐를 활용해 해결한 문제.

• 우선 ramen이라는 리스트에 데드라인을 기준으로 오름차순 정렬한다.
• 이후 heap을 생성하여 n loop 만큼 아래 로직을 반복한다.
• heap에 ramen 수를 넣는다. 이때 만일 힙 개수가 ramen 리스트 내 데드라인보다 크다면 heap의 최소 크기를 빼준다.
  -> 결과적으로 힙에 남은 값들을 모두 더해주면 라면을 최대로 얻을 수 있다.