백준 22252 정보 상인 호석 / python

문제 : 22252

풀이 point

이 문제는 정렬로는 풀 수 없다. 정렬의 시간복잡도는 O(nlogn)으로 최악의 경우 10만의 데이터가 있을 때 nlong을 10만번 반복해야하므로 1초 안에는 끝낼 수 없어 시간초과가 된다.

문제의 핵심은 가장 비싼 정보부터 산다는 것이다. 그러므로 모든 값들이 정렬되어 있을 필요는 없다.
가장 비싼 정보를 순서대로 뽑을 수 있으면 된다.

그럴때 필요한 자료구조가 바로 heap이다.
heap은 삽입, 삭제가 O(logn)이므로 정렬보다 훨씬 빠르게 진행할 수 있다. 설령 10만번 반복하더라도 시간초과에 걸리지 않는다. (보통 1초는 1억으로 가정)

풀이 방법

한줄로 모든 정보가 들어와서 헷갈릴 수 있는데 파이썬은 input().split()을 통해 구분해서 받으면 된다. (문자열로 들어오기 때문에 숫자는 int 변환이 필요)

heap을 통해 1번 쿼리일 경우는 해당 name을 가진 고릴라의 정보를 추가해준다.
2번 쿼리일 경우는 구매 개수만큼 정보를 삭제한다.

같은 name을 가진 고릴라가 여러번 나올 수 있고, 정보를 가지지 않은 고릴라에게 정보를 산다는 쿼리가 나올 수 있으므로 예외처리에 주의하자.

참고로 maxheap을 활용해야하기 때문에 -를 붙여서 넣어주면 된다.

풀이 코드

import heapq

ans = 0
gorilla = {}
for i in range(int(input())):
  query = input().split()

  name = query[1]
  k = int(query[2])

  if query[0] == '1':
    if name not in gorilla:
      gorilla[name] = []
    for i in query[3:]:
      heapq.heappush(gorilla[name], -int(i))
  else:
    if name not in gorilla:
      pass
    else:
      for i in range(min(k, len(gorilla[name]))):
        ans += -heapq.heappop(gorilla[name])

print(ans)