[백준] 1202 보석

✔️ 문제 링크

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

💡핵심 아이디어

1️⃣ 가방의 크기가 작은 것부터 탐색하고 그 중에서 보석이 가장 큰 것을 골라 택한다.(가방의 크기가 클 수록 선택권이 많아지니깐 적은 것 부터)

2️⃣ 보석의 무게가 작은 것 부터 선택할 수 있는 후보군에 넣고 우선순위 큐(heapq이용)을 사용하여 현재 후보군 중 가장 값어치가 높은 것 부터 넣어주도록 한다.

❗️오답 이유

1️⃣ 너무 복잡하게 생각하여 union-find알고리즘을 사용하려다가 실패 -> 좀 더 생각만 잘 했으면 훨씬 간단하게 풀 수 있었다.

❗️ input() VS sys.stdin.readline()

이 부분의 유무로 시간초과 문제를 해결할 수 있음을 보았다.

input()

• 사용자의 입력을 받고 문자열로 변환 후 추가 strip을 진행하기 때문에 sys.stdin.readline()보다 상대적으로 속도가 느림
  
• 내장 함수로 취급
• 더 이상 입력 없는 경우 수행되면 EOFerror를 반환

sys.stdin.readline()

• input()과 달리 개행 문자 또한 입력을 받을 수 있음
• file object로 취급 : 사용자 입력 buffer를 하나 만들어 그 buffer에서 읽어들임
• 더 이상 입력이 없어도 수행이 된 경우 빈 문자열을 반환

⭐️ 소스 코드

import heapq
from sys import stdin

input = stdin.readline

if __name__ == '__main__':
    N, K = list(map(int, input().split()))

    jewelry_list = []
    bag_list = []
    heap = []

    for _ in range(N):
        M, V = list(map(int, input().split()))
        jewelry_list.append((M, V))

    for _ in range(K):
        C = int(input())
        bag_list.append(C)

    jewelry_list.sort(key=lambda x: -x[0])
    bag_list.sort()

    ans = 0

    heap = []

    for bag in bag_list:
        while len(jewelry_list) != 0:
            search = jewelry_list.pop()
            if search[0] > bag:
                jewelry_list.append(search)
                break
            else:
                heapq.heappush(heap, (-search[1], search[1]))

        if len(heap) != 0:
            search = heapq.heappop(heap)
            ans += search[1]

    print(ans)