[Softeer 소프티어, 파이썬] 금고털이 - 레벨 2 | 최대힙 구현

📌 소프티어 Level 2 : 금고털이

별 2개짜리 문제라 다소 간단한데, 최대한 효율성 있게 풀고 싶어서 최대힙을 구현해 풀었다!

📝 내 답안

import sys
from heapq import heappush,heappop

w,m = map(int,sys.stdin.readline().split(" "))
value = []
answer = 0
# m가지 보석의 무게당 가격 heapq에 넣기, 최대힙 구현
for _ in range(m):
    w2,c = map(int,sys.stdin.readline().split(" "))
    heappush(value,(-c,w2))

while value and w > 0:
    c, w2 = heappop(value)

    if w >= w2:
        answer += w2 * -c
        w -= w2
    else:
        answer += w * -c
        w = 0

print(answer)

사실 최대힙으로 풀지 않고 리스트와 for문만으로도 구할 수 있는 간단한 문제인데,
리스트를 활용하면 O(N), heap을 사용하면 시간복잡도가 O(logN)이어서 차이가 꽤 난다.