[백준/Python] 22252 정보 상인 호석

https://www.acmicpc.net/problem/22252

풀이

• 1 정보 파는 고릴라이름 , k개 , 정보의 가치
• 2 정보 살 고릴라 이름 , 구매할 정보 개수
• 시간제한 2초 , 쿼리 최대 수 1e5 , 정보 리스트의 원소 최대 개수 1e5 , 최대 고릴라의 수 1e5 , 최대 정보를 구매 할 수 1e5
• 최악의 경우 : 1e5 * (파이썬 리스트 정렬 nlogn) → 시간초과 ⇒ 정렬해서 큰 값 뽑아내는거 아님
• 우선순위큐 힙큐 사용
• 1일시 hash_map에서 고릴라를 찾고 데이터를(힙큐 속성) 넣어준다
• 2일시 hash_map에서 고릴라를 찾고 힙큐를 꺼내서 데이터를 뽑아내고 다시 저장

나의 실수 코드

import heapq

n=int(input())
hash_map={}
result=0
for _ in range(n):
    data=list(input().split())
    if data[0]=='1':
        if data[1] not in hash_map.keys():
            li=[]
            for i in data[3:]:
                i=int(i)
                li+=[(-i ,i)]

            hash_map[data[1]]=li

        else:
            li=[]
            for i in data[3:]:
                i=int(i)
                li+=[(-i,i)]
            hash_map[data[1]]+=li

    else:
        if data[1] in hash_map.keys():
            li=hash_map[data[1]]
            for _ in range(int(data[2])):
                if li:
                    value=heapq.heappop(li)
                    result+=value[1]
                else:
                    break

print(result)

또 실수 코드

import heapq

n=int(input())
hash_map={}
result=0
for _ in range(n):
    data=list(input().split())
    if data[0]=='1':
        if data[1] not in hash_map.keys():
            li=[]
            for i in data[3:]:
                i=int(i)
                li+=[(-i ,i)]
            
            heapq.heapify(li)
            hash_map[data[1]]=li

        else:
            li=[]
            for i in data[3:]:
                i=int(i)
                li+=[(-i,i)]

            heapq.heapify(li)
            hash_map[data[1]]+=li

    else:
        if data[1] in hash_map.keys():
            li=hash_map[data[1]]
            for _ in range(int(data[2])):
                if li:
                    value=heapq.heappop(li)
                    result+=value[1]
                else:
                    break

print(result)

정답 코드

import heapq

n=int(input())
hash_map={}
result=0
for _ in range(n):
    data=list(input().split())
    if data[0]=='1':
        if data[1] not in hash_map.keys():
            li=[]
            for i in data[3:]:
                i=int(i)
                li+=[(-i ,i)]

            heapq.heapify(li)
            hash_map[data[1]]=li

        else:
            li=hash_map[data[1]]
            for i in data[3:]:
                i=int(i)
                heapq.heappush(li,(-i,i))
                

            
            

    else:
        if data[1] in hash_map.keys():
            li=hash_map[data[1]]
            for _ in range(int(data[2])):
                if li:
                    value=heapq.heappop(li)
                    result+=value[1]
                else:
                    break

print(result)

깨달은점

• hash_map에서 list의 형태로 꺼내왔다
• data의 값을 heapify로 한 다음 hash_map에서 꺼내온 list에 단순 더해서 틀렸다
• 그 다음 list를 heapify로 변환 한뒤 list에 더했다 → 역시 틀렸다
• hash_map에서 꺼내온 list는 현재 heapd의 속성을 띄고 있다
  • 단순 리스트에 원소를 더해주는게 아니라 , heappush를 이용해서 list에 원소를 넣어주어야 한다
• heaify는 리스트를 힙의 구조로 변경해주는 것이다
  • 힙의 구조를 변경한 리스트를 힙큐에 단순 더하기만 하는 것은 무의미한 행동이다