[이코테] 정렬_카드 정렬하기 (python)

문제

나의 풀이

1. 실패: 세밀하게 계산 못한 실수..

def card_sort(arr):
    if len(arr) == 1: # 카드가 한장이면 바로 반환
        return 0
    check = arr[0]
    tail = arr[1:]
    left = [x for x in tail if x <= check]
    right = [x for x in tail if x > check]
    return card_sort(left) + [check] + card_sort(right)

n = int(input())
array = [int(input()) for _ in range(n)]

card = card_sort(array)

answer = card[0] * (n - 1)
for i in range(1, n):
    answer += card[i] * (n - i)
    
print(answer)

2. 힙

import heapq 
q = [] 
n = int(input())
for i in range(n):
    heapq.heappush(q, (int(input())))
 
result = 0
while len(q) > 1: # 두개씩 뽑아야 하므로
    now1 = heapq.heappop(q) # 비교대상 1
    now2 = heapq.heappop(q) # 비교대상 2
    heapq.heappush(q, (now1 + now2)) # 계산한 결과를 다시 q에 넣는다
    result += now1 + now2
print(result)