[백준] 1781번 컵라면 - 그리디알고리즘 파이썬

https://www.acmicpc.net/problem/1781

1781번: 컵라면

 

이번 문제는 https://techbrad.tistory.com/68 이 문제 유형과 동일하게 보여서 유형을 익숙하게 하고자 풀어보았다.

하지만..... 자꾸 시간초과가 발생했다. 컵라면이고 뭐고 너무 짜증이 났지만 또 다른 블로그를 참고하고 분석했다.

 

문제 접근 방법

이전에 풀었던 문제와 같이 점수가 높은 순서대로 maxheap을 구성하여 풀었다. 여러번 확인했으나 반목문이 두개여서 O(N2) 시간 복잡도 때문에 그런건지 자꾸 시간 초과가 발생했다.

import heapq

hq = []
N = int(input())
max_deadline = 0

for i in range(0, N):
  day, score = map(int, input().split())
  heapq.heappush(hq, (-score, day))
  if max_deadline < day:
    max_deadline = day
arr = [False] * (max_deadline + 1)

total = 0
while hq:
  score, day = heapq.heappop(hq)
  score = - score
  for i in range(day, 0, -1):
    if arr[i]:
      continue
    arr[i] = True
    total += score
    break
print(total)

 

 

제출 코드

import heapq

N = int(input())
problem_list = []

for _ in range(N):
    deadline, cup_ramen = map(int, input().split())
    problem_list.append([deadline, cup_ramen])

problem_list.sort(key= lambda x:x[0])

cup_ramen_heap = []
for problem in problem_list:
    heapq.heappush(cup_ramen_heap, problem[1]) #problem[1]은 각 문제의 컵라면 개수
    if len(cup_ramen_heap) > problem[0]:  #problem[0]은 각 문제의 데드라인, 데드라인을 초과하는 문제는 힙에서 제거
        heapq.heappop(cup_ramen_heap)

print(sum(cup_ramen_heap))

그래서 이렇게 min heap으로 변경했더니 시간초과가 해결되었다. 풀이는 아래의 링크를 클릭!!

 

[백준] 13904번 과제 - 그리디알고리즘 파이썬