[백준] 1715번 - 단어 정렬하기

아이디어

1. 데이터(오름차순 정렬된 상태)를 2개씩 추출해서 값을 더한다.
2. 더한 값을 다시 큐에 넣는다.
   위의 과정을 반복해서 최종 횟수를 구한다.

   데이터를 우선순위 큐에 저장하였기 때문에 오름차순 정렬이 자동으로 수행된다.

코드

# 단어 정렬하기
from queue import PriorityQueue

N = int(input())
que = PriorityQueue() # 우선순위 큐

for _ in range(N):
    que.put(int(input())) # 큐 데이터 삽입

result = 0
tmp = 0

for i in range(N-1): # N-1만큼 덧셈이 이루어지기 때문에 N-1만큼 반복문 수행
    tmp = (que.get()+que.get()) # 큐 데이터 추출
    result += tmp # 결과값 저장
    que.put(tmp) # 데이터 2개를 더한 값을 우선순위 큐에 다시 넣어준다
print(result)