백준 2109 순회강연 파이썬

문제링크 : https://www.acmicpc.net/problem/2109

문제

작성자의 지능이슈(국어)

문제를 읽고, ‘날짜를 Key, 값을 Value로 구성하는 Key-Value를 구성해서 하나씩만 하면 되겠다' 라는 마음에 작성한 소스코드를 먼저 첨부한다

# kv_dict = {1: [20, 2], 3: [10], 2: [100, 8], 20: [5], 10: [50]}

import sys
input = sys.stdin.readline 
n = int(input().strip())

kv_dict = dict()

for _ in range(n) :
    v, k = map(int, input().split())

    if k in kv_dict.keys() :
        kv_dict[k].append(v)
    else :
        kv_dict[k] = [v]

hap = 0
for v in kv_dict.values() :
    hap += max(v)
print(hap)

이 소스코드는 특정한 날짜를 기준으로 가장 값이 큰 Value를 선택하는 방식이다. 그러나 다음 테스트케이스를 해결할수없었다

4
10 1
20 2
40 4
50 4

왜 틀렸는지 이해가되는가? Key로 주어지지않은날이여도, 날짜가 비었다면 순회강연을해서 돈을 더 벌수 있기때문이다.

(어쩐지 다른사람들 문제 푼거 보니까 전부다 heapq써서 풀었더라. 이것도모르고 맞왜틀? Pypy컴파일러가 고장났나싶었다)

사전지식 Heapq

일반적으로 최소힙, 최대힙을 필요할때 사용하는 라이브러리.

import heapq 로 선언하고, 사용할때는 heapq.{function} 방식으로 사용하는것이 특징이다.

사전지식 lambda sort

이걸 왜 써야했냐면, 데이터의 인풋 과정에서 ‘두번째 인자' 를 키로 정렬해야하는데

list(map(int, input().split()) 대신에 p,d = map(int, input().split()) 이후에 리스트에 넣을때 d,p 순서대로 넣으면 lambdasort를 안써도 된다

전체 소스코드

import heapq

n=int(input())
lst=[]
for i in range(n):
  lst.append(list(map(int, input().split())))

lst.sort(key=lambda x: (x[1]))
p_list=[]
for i in lst:
  heapq.heappush(p_list, i[0])
  if (len(p_list)>i[1]):
    heapq.heappop(p_list)

print(sum(p_list))