[BOJ 1202] 그리디 알고리즘, 우선순위 큐와 힙

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

1202번: 보석 도둑

오답 코드

import sys
sys.setrecursionlimit(1000000)

def FastInput():
    return sys.stdin.readline().rstrip()


def BinarySearch(array, target):
    if len(array) == 0:
        return None
    left = 0
    right = len(array)-1
    while left <= right:
        mid = (left + right)//2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if array[mid] < target:
        if mid == len(array)-1:
            return None
        return mid+1
    else:
        return mid


jewel_num, bag_num = map(int, FastInput().split())
jewel_list=[]
for i in range(jewel_num):
    jewel_weight , jewel_price = map(int, FastInput().split())
    jewel_list.append((jewel_price, jewel_weight))

bag_storage_list = []
for i in range(bag_num):
    bag_max_weight = int(FastInput())
    bag_storage_list.append(bag_max_weight)

jewel_list.sort()
jewel_list.reverse()
bag_storage_list.sort()

total_price = 0
for jewel_price, jewel_weight in jewel_list:
    appro_bag_idx = BinarySearch(bag_storage_list, jewel_weight)
    if appro_bag_idx == None:
        continue
    total_price += jewel_price
    # del(bag_storage_list[appro_bag_idx])
    bag_storage_list = bag_storage_list[:appro_bag_idx] + bag_storage_list[appro_bag_idx+1:]

print(total_price)

#리스트가 엄청 클 때 일회적인 알고리즘을 반복적으로 수행하기 위해, del 같은 함수를 계속 사용하는 것은 지나치게 연산이 많아진다.

가장 비싼 보석부터 최대한 작은 가방에 넣어보는 방식이다.

기본적인 설계 자체는 시간복잡도가 크지 않아 보였으나

정렬된 리스트에서 원소를 하나씩 제거하는 과정을 반복하는 것이 시간초과를 야기했다.

 

del 함수의 경우 O(n)의 시간복잡도를 가지고 있어, 부적절하였다.

 

힙을 활용한 우선순위 큐를 통해 문제를 해결하는 것이 모범답안이었다.

모범답안

import sys
import heapq

input = sys.stdin.readline
n, k = map(int, input().split())
items = []
bag = []
candi = []
answer = 0
for _ in range(n):
    # 보석 무게 기준 최소 힙 삽입
    heapq.heappush(items, list(map(int, input().split())))
for _ in range(k):
    bag.append(int(input()))
# 가방 오름차순 정렬
bag = sorted(bag)

for cap in bag:
    # 가방 작은거 부터 꺼내면서 그 가방에 들어가는 보석일단 다 꺼냄.
    # 꺼내서 값을 기준으로 최대힙에 넣음
    while items and items[0][0] <= cap:
        heapq.heappush(candi, -heapq.heappop(items)[1])
    # candi에 현재 가방에 들어갈 수 있는 보석 다들어있음.(최대힙)
    # 이 중 하나 빼면 됨.
    if candi:
        answer += abs(heapq.heappop(candi))
print(answer)

힙 자료구조를 활용하여 그리디 알고리즘을 구현하였다.

또한 내 풀이와 달리 가장 비싼 보석을 가장 가벼운 가방에 넣는것이 아니라 가장 가벼운 가방에 가장 비싼 보석을 넣는 방식으로 설계하였다.

 

Feedback

1. 그리디 알고리즘을 풀 때 접근 방식을 다각적으로 고민하자
2. 오름차순, 내림차순으로 작업을 수행할 때, 힙 자료구조의 사용으로 del 함수에 의존하는 상황을 피할 수 있음을 기억하자.