[백준] [골드4] [Heap] 카드 정렬하기

카드 정렬하기

1715번: 카드 정렬하기

 

 

• 내 풀이 - 오답
  • 가장 처음에는 heap을 써야하는 문제인지 몰르고 리스트로 풀었음
  • → 앞에서 더한 값들이 뒤에값보다커질 수 있기 때문에 계속 sort해줄거 아니면 리스트 x
•  계속(n번) 최소인 값을구해야 하는 경우 heap사용
  • → heap 사용한 첫 풀이: 오답

 

• heapq.heappush( heap , value ) 
  • 값이 삽입된 후에 최소힙 구조가 됨
• heapq.heappop( heap )
  • -> 최소힙의 루트가 반환되는 것
• 최소힙 루트가 반환되지 않고 순서대로 다음값이 반환된다고 생각해서 오답!

import heapq
n=int(input())
hp=[]
result=0

for _ in range(n):
    m=int(input())
    if not hp:
        heapq.heappush(hp, m)
        continue
    x=heapq.heappop(hp) #이 부분에서 앞에서 넣은 30이 아니라 40이 반환된다고 생각해서 틀림
    result+=m+x 
    heapq.heappush(hp,m+x)

print(result)

'''
10 20 - 30
30 40- 70
70 50 - 120

10 20 / 10 20 40 / 10 20 40 50
'''

 

• 재풀이
  • heap을 사용하면 hp에 들어있는 값 중 계속해서 최소값 2개가 나오는 것

#시간복잡도를 줄이기 위해 heap 사용
import heapq
n=int(input())
hp=[]
result=0

#값을 모두 받아온 후에 계산 따로
for i in range(n):
  heapq.heappush(hp, int(input()))

while len(hp)>1:
  #hp에 들어있는 값중 계속해서 최소값 2개가 나오는 것
  x1=heapq.heappop(hp)
  x2=heapq.heappop(hp)

  result+=x1+x2
  heapq.heappush(hp,x1+x2)
  
print(result)