백준(G4) 1715번: 카드 정렬하기(파이썬, Python3)

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

1715번: 카드 정렬하기

이 문제는 이렇게 쉽다고?? 이런 생각이 들었던 문제 같다.

 

첫째 줄에 카드의 개수가 주어진다. 둘째 줄부터는 카드가 주어진다.

ex) 카드가 10,20,40 이렇게 주어지면 (10 + 20) + (30 + 40) 이렇게 계산을 한다.

이것을 보고 카드를 오름차순으로 정렬을 하고 리스트를 하나 만든 뒤, 더한 값을 리스트에 추가할 생각을 했다.

heap = []
num = int(input())
for i in range(num):
    heapq.heappush(heap,int(input()))

heap이라는 리스트를 만든 뒤, for 반복문을 이용해서 heap에 최소 힙을 준수해서 숫자들을 넣었다.

만약 heapq 모듈을 모른다면 https://solution-is-here.tistory.com/114

백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명

이 사이트를 보고 오길 바란다.

 

result_list = []
while heap:
    if len(heap) == 1:
        break
    else:
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        third = first + second
        result_list.append(third)
        heapq.heappush(heap,third)

그 후, heap의 길이가 1이 되면 종료 하는 while 반복문을 만들었다.

heap의 길이가 1이 아니면 heap에서 heappop 함수를 이용해서 가장 작은 함수 2개를 추출한 뒤 더한 값을 result_list에 넣어주고 heappush 함수를 이용해서 heap에 넣어줬다.

 

result = 0
for i in range(len(result_list)):
    result += result_list[i]
print(result)

result_list의 길이만큼 반복하는 반복문에서 result라는 변수에 result_list의 값들을 더해줬다.

그다음 출력하면 끝이다.

 

정답코드:

 

import sys
import heapq
input = sys.stdin.readline
heap = []
num = int(input())
for i in range(num):
    heapq.heappush(heap,int(input()))
result_list = []
while heap:
    if len(heap) == 1:
        break
    else:
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        third = first + second
        result_list.append(third)
        heapq.heappush(heap,third)
result = 0
for i in range(len(result_list)):
    result += result_list[i]
print(result)