백준 문제풀이 - 2109 번

링크 -> https://www.acmicpc.net/problem/2109

1. 요약 및 풀이방법

저명한 학자에게 n개의 강연 요청이 들어옵니다.
이때 각 강연의 강연료와 기한이 주어지면,
가장 많은 돈을 벌 수 있도록 순회강연을 하는 경우를 구하는 문제입니다.

heapq 모듈을 이용해 문제를 해결하였습니다.
우선 강연 제안을 기한을 기준으로 오름차순으로 정렬한 후,
하나씩 heapq를 이용해 리스트에 추가합니다.
이때, 리스트의 길이가 기한보다 큰 경우, 기한을 지난 강연이므로
현재까지 추가한 강연 중 가장 강연료가 적은 강연을 heappop을 이용해 제거합니다.
이렇게 모든 강연에 대해 강연료를 추가 합니다.

2. Code

import sys
import heapq

def main():
    N = int(input())
    fees = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]
	
    # 날짜를 기준으로 오름차순 정렬
    fees.sort(key=lambda x: x[1])

    sums = []
    for fee, date in fees:
    	# 강연료를 sums list에 추가
        heapq.heappush(sums, fee)
        # sums 길이보다 data가 작으면 기한을 넘긴 강연이기 때문에,
        # 가장 작은 강연료를 heappop으로 제거
        if len(sums) > date:
            heapq.heappop(sums)
    print(sum(sums))

if __name__ == "__main__":
    main()

3. 학습 내용

이번 문제에서는 heapq에 대해 학습 하였습니다.
heapq 모듈을 이용하면 일반적인 리스트를 최소 힙 처럼 다룰 수 있습니다.
하지만 별개의 자료구조가 아닌 python의 일반적이 리스트를 다루는 것으로,
heapq 모듈의 함수를 사용 할 때마다, 해당 리스트를 인자로 넘겨주어야 합니다.

이렇게 heapq를 이용해 리스트를 추가하고 제거한 리스트가 그냥 최소 힙 입니다.

위 코드에서 heappush, heappop 을 이용해 원소를 추가하고 제거했음을 볼 수 있습니다.

4. 결과