백준 / 보석 도둑 / 1202번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 보석 도둑 / 1202번 (골드 2단계)

문제 사이트: https://www.acmicpc.net/problem/1202

 

문제 설명

---

나의 풀이

import sys
import heapq

def solution(bags, jewel):
    # 결과 값
    answer = 0
    result = []  # 보석을 담을 최대 힙

    # 정렬 (보석: 무게 기준 오름차순, 가방: 오름차순)
    bags.sort()
    jewel.sort()

    # 가방을 하나씩 확인하며 적절한 보석을 최대 힙에 넣고 가장 비싼 걸 선택
    for bag in bags:
        while jewel and jewel[0][0] <= bag:
            heapq.heappush(result, -jewel[0][1])  # 최대 힙을 위해 음수 변환
            heapq.heappop(jewel)

        if result:
            answer -= heapq.heappop(result)  # 가장 비싼 보석 선택

    return answer

def main():
    # 빠른 입력을 위해 sys.stdin.read 사용
    input = sys.stdin.read
    data = input().split()

    n = int(data[0])
    k = int(data[1])

    jewel = []
    bag = []

    index = 2
    for _ in range(n):
        m = int(data[index])
        v = int(data[index + 1])
        jewel.append([m, v])
        index += 2

    for _ in range(k):
        bag.append(int(data[index]))
        index += 1

    # 빠른 출력
    sys.stdout.write(str(solution(bag, jewel)) + "\n")

if __name__ == "__main__":
    main()

import heapq


def solution(bags, jewel):
    # 결과 값
    answer = 0

    # 결과 값을 담을 배열
    result = []

    # 정렬 오름차순으로 정렬
    bags.sort()
    jewel.sort()

    # 가방을 하나씩 꺼내기
    for bag in bags:
        # 보석들과 비교를 하면서 가방에 들어가는 가장 큰 보석을 찾아서 넣는다.
        while jewel and jewel[0][0] <= bag:
            # 최대 힙 음수를 붙이면 사용 가능
            heapq.heappush(result, -jewel[0][1])
            heapq.heappop(jewel)
        if result:
            answer -= heapq.heappop(result)

    return answer


def main():
    # N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
    # K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
    n, k = map(int, input().split())

    jewel = []  # 보석

    bag = []  # 가방

    # 각 보석의 정보 Mi와 Vi (무게 Mi와 가격 Vi)
    for _ in range(n):
        m, v = map(int, input().split())
        jewel.append([m, v])

    # 가방 사이즈
    for _ in range(k):
        size0 = int(input())
        bag.append(size0)

    # 출력
    print(solution(bag, jewel))


if __name__=="__main__":
    main()

위 풀이도 알고리즘은 맞지만 sys 입출력 과정에서 틀리게 된 풀이입니다! 1,000,000개 이상의 입출력시 sys을 사용하지 않으면 시간 초과가 많이 발생하니깐 참고하시면 좋을 것 같습니다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/179

[자료구조] 힙(Heap)