백준 1202 - 파이썬

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

1202번: 보석 도둑

문제 해결

이 문제를 처음에 보고 생각난 풀이 방법은 다음과 같다.

 

1. 가방무게와 보석무게 모두 정렬 후 첫번째 보석부터 차례대로 진행

2. 현재 보석의 무게를 모든 가방에 넣을 수 있다면, 최대 무게가 가장 적은 가방에 입력.

3. 만약 가방에 이미 다른 보석이 먼저 있다면, 먼저 들어있는 보석과 현재 넣으려 하는 보석의 가격 비교하여 더 비싼 보석 넣음.

4. 위 과정 반복 후 가방에 있는 모든 보석의 가격 합한 후 출력

 

코드는 아래와 같다.

import sys

n, k = map(int, sys.stdin.readline().split())

jewelList = []
bagWeight = []
bagList = [0] * k

for _ in range(n):
  jewelList.append(tuple(map(int, sys.stdin.readline().split())))

for _ in range(k):
  bagWeight.append(int(sys.stdin.readline()))

jewelList.sort()
bagWeight.sort()

# jewelList = [(1, 65), (2, 99), (5, 23)]
# bagWeight = [2, 10]

for i in range(k):
  for j in range(n):
    if jewelList[j][0] < bagWeight[i]:
      if bagList[i] == 0:
        bagList[i] = jewelList[j][1]
      else:
        if bagList[i] < jewelList[j][1]:
          bagList[i] = jewelList[i][1]
          
print(sum(bagList))

하지만 위 풀이는 시간 초과가 났다. 혹시나 다른 방법이 있나 고민해봤지만 찾지 못하여 다른 사람의 풀이를 찾아 보왔다.

 

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())
jew = []

for _ in range(n):
  heapq.heappush(jew, list(map(int, sys.stdin.readline().split())))

bags = []

for _ in range(k):
  bags.append(int(sys.stdin.readline()))

bags.sort()

answer = 0
tmp_jew = []
for bag in bags:
  while jew and bag >= jew[0][0]:
    heapq.heappush(tmp_jew, -heapq.heappop(jew)[1])

  if tmp_jew:
    answer -= heapq.heappop(tmp_jew)
  elif not jew:
    break

print(answer)

아이디어 자체는 나와 동일하지만 차이점을 찾아 본다면 최대힙과 최소힙을 사용하였다는 점이다.

핵심은 파이썬의 heapq는 맨 앞에 있는 수를 기준으로 최소힙 정렬된다는 점을 활용하여, 처음에는 보석의 무게와 가치를 저장하여 무게를 기준으로 정렬을 진행하며 heappop을 진행하였고, 가방보다 무게가 작은 보석을 tmp_jew에 최대힙으로 저장하였다. 이 과정을 가방의 개수만큼 반복하여 추출하게 되면 가방에 들어갈 수 있는 보석 중 가치가 가장 높은 보석의 합을 구할 수 있게 된다.

 

이번 문제를 풀면서 느낀 점은 문제를 푸는 아이디어를 떠올리는것도 중요하지만 기존에 이미 구현된 자료구조를 활용하여 시간을 단축하는 것 또한 중요한 것 같다. 아직 힙이나 스택, 큐 등의 자료구조를 활용하는것이 익숙하지는 않지만 계속 사용하면서 익숙해져야 되겠다.