새로운 자료구조 ... 우선순위큐!

1. 내 풀이: 실패

import sys
input = sys.stdin.readline

n = int(input())
num = []
for _ in range(n):
    num.append(int(input()))

if len(num) == 1:
    print(num[0])
else:
    num.sort()
    total = [num[0]] + [0]*(n-1)
    for i in range(1, n):
        total[i] = total[i-1] + num[i]
    print(total)
    print(sum(total[1:]))

처음에는 이게 왜 틀렸지 하다가 결국 모르겠어서 인터넷의 다른 풀이를 봤다. 사람들이 배열로 풀면 시간 초과가 난다고 해서 새로운 방법 익히기 시도!

2. 다른 풀이

import sys, heapq

N = int(sys.stdin.readline())
cards = [int(sys.stdin.readline()) for i in range(N)]
heapq.heapify(cards)
cnt = 0

while len(cards) > 1:
    tmp = heapq.heappop(cards) + heapq.heappop(cards)
    heapq.heappush(cards, tmp)
    cnt += tmp
    
print(cnt)

풀이출처: https://codinghejow.tistory.com/201

우선순위 큐 라는 알고리즘을 통해 구현된 풀이이다. 여기서는 heapq라는 모듈에 의해서 구현되는데, queue.Priorityqueue와는 다르게 리스트 형태로 우선순위큐를 다룰 수 있다는 점에서 큰 장점이 있다.

여기는 이 heapq를 다루기 위해 필요한 조작 방법들이 담긴 사이트이다.

3. 다른 풀이

heapq는

• 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조
• 그렇기 때문에 삽입 or 삭제와 동시에 정렬
• 기존 리스트로 정렬할 때 시간초과가 난다면 우선순위큐 적용하기!