boj.kr/1202 보석 도둑 (gold2) 파이썬 풀이

오답풀이

- 제시된 2개 테스트 케이스는 통과했으나 제출시 시간초과했다.

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

items = []
for _ in range(N):
    items.append(list(map(int, input().split())))

from collections import deque

bags = deque()
for _ in range(K):
    bags.append(int(input()))

items = sorted(items, key = lambda x:x[1], reverse=True)

tot = 0
for item in items:
    # av_bags = sorted(list(filter(lambda x: x>=item[0], bags)))
    av_bags = [x for x in bags if x>=item[0]]
    if len(av_bags) > 0:
        bags.remove(min(av_bags))
        tot += item[1]

print(tot)

 

정답풀이

- 우선순위큐를 사용해 최소 가방무게 찾기, 최대 가격의 보석 찾기, 요소 삭제 연산을 하면 이중 for문을 돌 때 보다 연산횟수를 절약할 수 있다.

 

1. 최소 heapq으로 [보석무게, 보석가격] 들을 모두 저장

2. 최소 heapq으로 가방의 무게들을 모두 저장

3. 가방들을 모두 순회하면서 아래를 반복

3.1. 가방들 중 최소용량을 가지는 가방을 heappop

3.2. 보석정보 목록이 비어있지 않고 꺼낸 가방이 존재하는 보석중 최소무게 이상의 용량인 경우 아래를 반복

3.2.1.  보석목록에서 해당 보석을 heappop하고 최대 heapq으로 해당 보석의 가격을 저장

3.3. 최대 heapq에 저장된 보석 가격이 있으면, 그중 최대값을 heappop하여 총합 tot 변수에 더하기

3.4. 보석들을 모두 heappop했으면 반복문을 종료

4. 총합 tot 변수 값을 출력

 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

import heapq
items = []
for _ in range(N):
    heapq.heappush(items, list(map(int, input().split())))

bags = []
for _ in range(K):
    heapq.heappush(bags, int(input()))

tot = 0
temp_items = []
while bags:
    bag = heapq.heappop(bags)
    while items and bag >= items[0][0]:
        heapq.heappush(temp_items, -heapq.heappop(items)[1])
    if temp_items:
        tot += -heapq.heappop(temp_items)
    elif not items:
        break

print(tot)

 

최소힙과 최대힙을 사용하면 최소값과 최대값을 O(logN)의 시간복잡도로 찾을 수 있다.

 

 

참고출처
"[백준] 1202 - 보석 도둑 💎 (Python) / 골드 2 / 정렬 / 그리디", bio-info.tistory.com, 2022년 10월 21일 수정, 2023년 6월 12일 접속, https://bio-info.tistory.com/195.