[BOJ / 백준] 1715 카드 정렬하기 python / 파이썬 우선순위 큐 / 힙

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

1715번: 카드 정렬하기

 

---

1) 요구사항 분석 : 문제 읽기

비교하는 회수만큼 출력

 

2) 설계 : 접근 방식

가장 효율적인 방법은 현재 배열에 남아있는 가장 작은 값 2개를 비교!

배열에서 가장 작은 값을 계속 찾아줘야하니까 -> 우선순위 큐, 최소힙을 이용

import heapq

그리고 두개의 합을 다시 힙에 푸시해주기!

처음에 95%에서 틀렸는데 입력이 1개일 때 예외처리를 안해줘서,,

입력으로 1개 묶음의 카드가 들어오면 얘는 비교를 안해줘도 되니까, 이 땐 0을 출력

# BOJ1715 카드 정렬하기
import sys
import heapq

input = sys.stdin.readline
n = int(input())
heap = []
for i in range(n):
    i = int(input())
    heapq.heappush(heap, i)
start = 0
ans = 0
while len(heap) > 0:
    tem = heapq.heappop(heap)
    if start == 0:
        start = tem
    else:
        ans += (start + tem)
        if len(heap) != 0:
            heapq.heappush(heap, start + tem)
        start = 0
if start != 0:
    ans += start
if n == 1:
    ans = 0
print(ans)