[Algorithm] - HEAP(우선 순위 QUEUE)

Heap - 우선 순위 Queue

---

Pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 , 우선 순위가 가장 높은 원소가 나온다.

• 원소의 추가 O(LogN)
• 우선 순위 높은 ITEM 확인 O(1)
• 우선 순위 높은 순서 제거 O(LogN)
• 이진 검색 트리와 Heap 은 다른 자료 구조다.

import heapq

 

BOJ 1715번 - 카드 정렬하기

---

IDEA ​

​1. 작은 값 2개 값을 더하는게 최소의 경우이다. ( GREEDY )

-> 작은 값을 더하지 말고 다른 값을 더하였을 경우보다 더 작은 경우가 발생 불가능!

2. 수의 범위가 1000일 때, 10만개인 경우에 INT형의 범위를 벗어나는가?

-> INT형의 범위를 벗어나지 않아 별도로 생각하지 않아도 된다.

3. 예외 처리 1개만 들어온 경우는 최소 값이 아닌 한번도 실행하지 않아, 0번으로 출력해야 된다.

 

import heapq
import sys
input = sys.stdin.readline

def solution ( n ) :
    temp = []
    answer = 0

    [heapq.heappush ( temp , int(input() ) ) for _ in range ( n ) ]
        
    # 예외 처리
    if n == 1 :
        return 0

    while len(temp) > 1 :
        first , second = heapq.heappop( temp ) , heapq.heappop( temp )
        change_value = first + second
        heapq.heappush ( temp , change_value )
        answer += change_value
    
    return answer

n = int ( input() )
print ( solution ( n ) )