백준 1202 보석 도둑 파이썬 풀이

난이도 : 골드2

풀이일 : 2403247

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

1202번: 보석 도둑

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

오답 코드 -> 3% 틀렸습니다.

import sys, heapq

N, K = list(map(int, sys.stdin.readline().split()))
jewels = []
bags = []
value = []

for _ in range(N):
    M, V = list(map(int, sys.stdin.readline().split()))
    heapq.heappush(jewels, [M, V])

for _ in range(K):
    C = int(sys.stdin.readline())
    heapq.heappush(bags, C)
i = 0
while i < K:
    i += 1
    C = heapq.heappop(bags)
    while jewels and jewels[0][0] <= C:
        M, V = heapq.heappop(jewels)
        if len(value) < K:
            heapq.heappush(value, V)
        else:
            if value[0] < V:
                heapq.heappop(value)
                heapq.heappush(value, V)

print(sum(value))

• jewel : 보석 무게, 가치 정보를 담을 배열. heapq로 정렬
• bags : 가방 무게 제한 정보를 담을 배열. heapq로 정렬
• value : 각 가방에 담을 수 있는 무게들을 저장할 배열, heapq로 정렬
• while i < K : 가방의 수 만큼 반복하며 각 가방 정보를 가지고 보석의 정보와 비교
• 현재 value의 길이가 K 보다 작다면, value에 현재 보석의 정보를 추가
• 현재 value의 길이가 K와 같다면, value 최소값과 현재값을 비교 후 교체하거나 유지  

틀린 이유

• len(value)와 K를 비교해 value에 보석 정보를 추가하는 로직 때문에, 현재 가방에 담을 수 있는지를 제대로 확인하지 못한 채 보석들을 가방에 담을 수 있는 것처럼 처리되었다.

---

풀이 코드

import sys, heapq

N, K = list(map(int, sys.stdin.readline().split()))
jewels = []  # 보석 무게, 가치 정보
bags = []  # 가방 무게 정보
temp = []  # 가방에 들어갈 수 있는 보석 정보
value = 0  # 총 가치

for _ in range(N):  # 보석 정보 입력 처리
    M, V = list(map(int, sys.stdin.readline().split()))
    heapq.heappush(jewels, [M, -V])

for _ in range(K):  # 가방 정보 입력 처리
    C = int(sys.stdin.readline())
    bags.append(C)

bags.sort()  # 가방 정렬

for bag in bags:
    # 보석 무게가 현재 가방 무게보다 작거나 같은 경우
    while jewels and bag >= jewels[0][0]:
        # 보석 정보 temp 저장
        M, V = heapq.heappop(jewels)
        heapq.heappush(temp, V)
    # 담을 수 있는 보석이 있다면, 가장 가치가 높은 것 담기
    if temp:
        value -= heapq.heappop(temp)

print(value)

코드 변화

• bags 직접 정렬. heapq를 사용한 방식에서 직접 정렬로 변경
• temp : 현재까지 무게의 가방에 담을 수 있는 보석 정보를 담는 배열. heapq로 정렬
• value : 리스트 형식에서 숫자 형식으로 변경
• jewels : 가치를 -V로 저장하여 가장 큰 값부터 pop 할 수 있도록 수정
• 현재 가방에 담을 수 있는 무게의 보석 정보를 모두 temp에 추가
• 담을 수 있는 보석이 있다면, 담을 수 있는 보석 중 가장 가치가 큰 값을 pop 하여 value에 합산

---

느낀점

• 가장 최근에 푼 문제랑 비슷해보여서 쉽게 풀 수 있을 것 같았는데, 꽤 헤매면서 풀었다. 왜 티어 차이가 한 단계밖에 안나는지 의아하기도 하고.
• heapq 하나 배우기 싫어서 미뤄왔던 옛날이 생각나면서, 조금씩 공부하면 풀 수 있는 문제는 훨씬 더 많아지는 것 같다. 자료형 공부도 해나가야지.