백준 - 보석 도둑 / Gold 2 / 1202번 / Python

문제 📋

백준 - 보석 도둑

풀이 📝

import sys
import heapq


def solution(gems, bags):
    answer = 0
    values = []

    gems.sort()
    bags.sort()

    for bag in bags:
        while gems and gems[0][0] <= bag:  # 담을 수 있는 보석들 중에서
            heapq.heappush(values, -gems[0][1])  # 가격을 최대힙에 저장(음수로 저장하여 최소힙을 최대힙으로)
            heapq.heappop(gems)  # 가격 저장한 보석은 버리기

        if values:  # bag 무게 이하 보석 가격 다 저장했으면
            answer -= heapq.heappop(values)  # 제일 가치가 높은 가격 더하기(음수니까 빼기)
    return answer


n, k = map(int, sys.stdin.readline().split())
gems = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
bags = [int(sys.stdin.readline()) for _ in range(k)]

print(solution(gems, bags))

어려운 그리디 문제이다.
처음에 구현했던 풀이가 시간 초과가 나서 여러 코드를 참고하였다.

먼저 그리디 문제를 만났을 때 "최적의 선택"을 어떻게 할 것인지 가 매우 중요한 것 같다.
이 문제에서 "최적의 선택"을 판단하는 기준은 바로 "시간 복잡도"였다.

보석의 개수와 가방의 개수가 각각 최대 30만이기 때문에
아무리 느려도 시간 복잡도를 O(nlogn)이내로 구현해야 한다.

또한 단순히 정렬만 해서 순회하면 되는 게 아니라
가방마다 넣을 수 있는 보석들을 다모 아서 그것들 중 가장 비싼 보석을 반환해야 했다.

즉, 정렬된 리스트에 삽입과 삭제가 빈번했고 이미 가방을 순회할 때 O(n)의 시간 복잡도가 존재했기 때문에 O(logn) 이내로 삽입 삭제가 가능해야 했다.
따라서 우선순위 큐를 사용하여 문제를 해결했다.