[백준][구현] 22252. 정보 상인 호석

22252. 정보 상인 호석

 

• 첫 풀이
  • 처음에 heap으로 풀었는데 for문 안에서 힙이 비었는지 체크하고 pop했더니 시간초과 남
    • → min(int(quest[2]), len(dic[quest[1]])) 로 for문 돌아야함

import heapq
from collections import defaultdict

q = int(input())
dic = defaultdict(list)
answer = 0
for _ in range(q):
    quest = list(input().split())

    if quest[0] == '1':
        for i in range(int(quest[2])):
            heapq.heappush(dic[quest[1]], -int(quest[3+i]))
    else:
        if dic[quest[1]]:
            for _ in range(int(quest[2])):
                if not dic[quest[1]]:
                    continue
                answer += -heapq.heappop(dic[quest[1]])

print(answer)

# 힙이 비었는지 비교하는 부분에서 시간초과
# min 값으로 비교해서 있는 만큼만 돌게 해야 시간 효율 높일 수 있음
for _ in range(min(int(quest[2]), len(dic[quest[1]]))):
    answer += -heapq.heappop(dic[quest[1]])

 

• 두번째 풀이
  • heap으로 안되서 sort로 품

import heapq
from collections import defaultdict

q = int(input())
dic = defaultdict(list)
answer = 0
for _ in range(q):
    quest = list(input().split())

    if quest[0] == '1':
        dic[quest[1]] += list((map(int, quest[3:])))
        dic[quest[1]].sort()
    else:
        if dic[quest[1]]:
            answer += sum(dic[quest[1]][-int(quest[2]):])
            dic[quest[1]] = dic[quest[1]][:-int(quest[2])]

print(answer)