[1744] 수 묶기 ( 수를 묶어서 최댓값 만들기, 우선순위 큐)

1744번: 수 묶기

 

분석

• 양수 : 가능한 큰 수들끼리 묶음
• 음수: 음수끼리 곱해서 양수로 더함
• 0 : 음수가 남는경우 0을 곱함
• 1 : 다 더함

 

풀이

import sys
input=sys.stdin.readline
from queue import PriorityQueue

pq = PriorityQueue() # 양수처리
mq = PriorityQueue() # 음수처리
one=0
zero=0

n=int(input())
for _ in range(n):
    data=int(input())
    if data>1:
        pq.put(data*-1) # 내림차순 정렬을 위해 -1을 곱해서 저장
    elif data==1:
        one+=1
    elif data==0:
        zero+=1
    else:
        mq.put(data)


sum=0

# 양수 처리
while pq.qsize() > 1:
    tmp= pq.get()*pq.get()
    sum+=tmp

if pq.qsize() > 0:
    sum+=pq.get()*-1

# 음수 처리
while mq.qsize() > 1:
        tmp = mq.get()*mq.get()
        sum += tmp

# 음수 큐에 데아터 남아있고 0이 한개도 없으면
if mq.qsize() > 0:
    if zero==0:
        sum+=mq.get()

sum+=one

print(sum)