[python] boj 1202 보석 도둑

 

1202번: 보석 도둑

우선 순위 큐라는 내용을 공부해놓고는 활용해보지도 못 하다가 이 문제를 통해서 잃어버린 기억을 되찾게 되었다.

 

우선 처음 우선 순위 큐를 인식하지 못 하고 푼 기본 아이디어부터~

 

기본 아이디어 1 (실패)

1. 보석과 가방에 대한 정보를 받아온다.
2. 보석은 가격에 따라 정렬하고 다음 우선순위로 보석 크기에 따라 정렬한다.
3. 가방은 크기에 따라 정렬한다.
4. 이중 반복문으로 가방을 순회하면서 보석을 순서대로 순회하면서 가방에 보석이 들어간다면 방문 처리하고 결과에 값을 반영한다.

코드

import sys
readlines = sys.stdin.readline

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

jewelrys = []
visited = [0] * N
bags = []

for n in range(N):
    jewelrys.append(list(map(int, readlines().split())))

for k in range(K):
    bags.append(int(readlines()))

jewelrys.sort(key=lambda x: (-x[1], x[0]))
bags.sort()

result = 0
for bag in bags:
    for j in range(N):
        if not visited[j] and jewelrys[j][0] <= bag:
            visited[j] = 1
            result += jewelrys[j][1]
            break

print(result)

결과

이중 반복문으로는 이 문제를 풀 수 없었습니다.

 

 

기본 아이디어 2 (성공)

우선 순위 큐를 활용하였는데 자세한 내용은 아래에서 개념을 익히고 풀었습니다.

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

1. 보석에 대한 정보를 받을 때 보석 크기를 기준으로 우선순위 큐에 넣어준다.
2. 가방도 마찬가지로 크기에 대한 기준으로 우선순위 큐에 넣어준다.
3. 가방을 우선순위 큐에서 heappop해서 cur_bag 변수에 넣어준다.
4. cur_bag의 값보다 작거나 같은 보석들을 모두 pop해서 temp 리스트에 보석 가격을 기준으로 heappush 해준다.
5. 위 작업이 끝나면 temp에서 가장 가격이 높은 보석을 뽑기 위해 heappop해준다.
6. 가방에 모든 보석을 담거나 temp가 다 떨어질 때 까지 3~5 과정을 반복한다.

코드

import sys, heapq
readlines = sys.stdin.readline

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

jewelrys = []
bags = []

for n in range(N):
    heapq.heappush(jewelrys, list(map(int, readlines().split())))

for k in range(K):
    heapq.heappush(bags, int(readlines()))

result = 0
temp = []
while bags:
    cur_bag = heapq.heappop(bags)

    while jewelrys and cur_bag >= jewelrys[0][0]:
        cur_jewelry = heapq.heappop(jewelrys)
        heapq.heappush(temp, -cur_jewelry[1])

    if temp:
        result += -heapq.heappop(temp)

print(result)

 

결론

우선순위 큐, 힙에 대한 공부가 부족했음을 느꼈다. 조만간 자료 구조 공부를 한 번 쫘아아악 해줘야겠다.