<import>
from queue import PriorityQueue
<생성 방법>
myque = PriorityQueue() # myque를 우선순위 큐로 생성
<기본 함수>
put(data) # 원소 추가
get() # 큐에서 데이터 꺼내기
qsize() # 큐 사이즈 가져오기
empty() # 큐가 비어있는지 확인
<import>
import heapq
<생성 방법>
mylist = [] # 리스트 생성
heapq.heappush(mylist, 1) # 리스트에 데이터를 넣을 때 heapq를 이용하여 저장
<기본 함수>
heappush(mylist, data) # data를 list(heap 자료구조) 형태로 저장
heappop(mylist) # list(heap 자료구조)에서 데이터 꺼내기
heapify(mylist) # 일반적인 list를 heap 자료구조로 변환
PriorityQueue는 객체 자체를 우선순위 큐 형태로 만들어서 사용하는 반면 heapq는 기본적인 list 객체를 대상으로 원소 삽입, 삭제(꺼내기) 등의 제공 함수를 통해 우선순위 큐를 구현한다.
from queue import PriorityQueue
N = int(input()) # 카드 묶음 개수
pq = PriorityQueue() # 우선순위 큐
for _ in range(N):
data = int(input())
pq.put(data) # 우선순위 큐에 데이터 저장
# 이렇게 우선순위 큐에 넣은 데이터들은 자동 정렬이 됨
data1 = 0
data2 = 0
sum = 0
while pq.qsize() > 1: # 우선순위 큐에 데이터가 하나만 남을 때까지
data1 = pq.get() # 카드 2개 묶음을 큐에서 뽑음
data2 = pq.get()
temp = data1 + data2
sum += temp # 카드 2개를 더하는데 필요한 비교횟수를 결과값에 더함
pq.put(temp) # 카드 2개의 합을 우선순위 큐에 다시 넣음
print(sum) # 결과값 출력
from queue import PriorityQueue
N = int(input())
plusPq = PriorityQueue()
minusPq = PriorityQueue()
zero = 0
one = 0
for i in range(N): # 데이터 분리 저장
n = int(input())
if n > 1:
plusPq.put(n*-1) # 양수 내림차순 정렬을 위해 -1을 곱하여 저장
elif n == 0:
zero += 1
elif n == 1:
one += 1
else:
minusPq.put(n)
sum = 0
while plusPq.qsize() > 1: # 2개 이상 남았을 때
data1 = plusPq.get() * -1
data2 = plusPq.get() * -1
sum += data1 * data2
if plusPq.qsize() > 0: # 1개가 남았을 때(홀수)
sum += plusPq.get() * -1
while minusPq.qsize() > 1:
data1 = minusPq.get() * -1
data2 = minusPq.get() * -1
sum += data1 * data2
if minusPq.qsize() > 0: # 1개가 남았을 때(홀수)
if zero == 0: # 0개수가 0개면 남은 수를 그냥 더함
sum += minusPq.get()
# (만약 음수가 1개 남았고 0도 있으면 곱해서 음수를 상쇄시켜버림)
sum += one
print(sum)