[백준] 카드 정렬하기 (python)

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

1715번: 카드 정렬하기

 

1. 내가 작성한 코드

import heapq
import sys

input = sys.stdin.readline

n = int(input().rstrip()) #입력 횟수

heap = []

for i in range(n):
  heapq.heappush(heap,int(input().rstrip())) #heap에 모든 값 push

answer = 0

while True:

  if len(heap) > 1:
    result = 0
    result = heapq.heappop(heap) + heapq.heappop(heap) #heap의 first,second 값 더하기
    answer += result #first, second를 더한 값 계속 더함
    heapq.heappush(heap, result) 
    
  if len(heap) == 1:
    break

print(answer)

 

heap 자료구조를 이용해서 해결해야하는 문제이다.

 

❗ python의 heapq 모듈은 최소힙을 제공해주기 때문에 heappop을 하면 heap의 최솟값이 출력된다.

 

2. 문제 해결 과정

1. heap을 만들어주고, 모든 값을 push 해준다.

 

2. 제일 작은 두 수를 pop해서 꺼낸다.

 

3. 2번에서 꺼낸 두 수를 더해서 heappush를 해주고 원소가 하나 남을 때까지 2,3번 과정을 반복한다.

=> 이 때, 비교횟수를 저장할 answer이라는 변수를 새롭게 정의하고, 가장 작은 두 수를 더한 값을 더해준다.

 

예시)

heap 상태

10 10 20 40 => (10+10) 20 40 => (20+20) 40 => (40+40) #원소가 80으로 한 개 남으니 break

 

result 상태

0 => 20 => 20+40 => 20+40+80  #140.

 

따라서 140이 출력됨

 

 

3. 메모

지금 힙자료구조를 배우고 있어서 아이디어를 금방 떠올릴 수 있었다.

 

최대/최소가 나올 경우는 heap을 한 번 떠올려보자