파이썬 | 백준 | 1744 | 수 묶기

solution

1. 수가 양수인 경우, 음수인 경우를 나눈다.

      양수 → 최대힙

      음수 → 최소힙

2. 우선순위 큐 사용

# 1744, 수 묶기
import sys
import heapq

N = int(sys.stdin.readline())
positive = []
negative = []
zero = False

for _ in range(N):
    num = int(sys.stdin.readline())
    if num > 0:
        heapq.heappush(positive, (-num, num))    # 양수
    elif num < 0:
        heapq.heappush(negative, num)   # 음수
    else:
        zero = True     # 0이 있는지

res = 0

# 양수
flag = 0
tmp1, tmp2 = 0, 0
while positive and positive[0][1] > 1:
    if flag == 0:
        tmp1 = heapq.heappop(positive)[1]
        flag = 1
    else:
        tmp2 = heapq.heappop(positive)[1]
        flag = 0
        res += tmp1*tmp2
# 양수의 개수가 홀수면 힙에 남아있는 수를 결과 res에 더한다.
if flag:
    res += tmp1
# 힙에 1 남아있으면 더함
while positive:
    res += heapq.heappop(positive)[1]

# 음수
flag = 0
while negative:
    if flag == 0:
        tmp1 = heapq.heappop(negative)
        flag = 1
    else:
        tmp2 = heapq.heappop(negative)
        flag = 0
        res += tmp1*tmp2
# 힙에 남아있는 수가 있는 경우 수열에 0이 있으면 0을 곱해서 0을 만듦(상쇄)
if flag:
    # 수열에 0이 없으면
    if not zero:
        res += tmp1

print(res)

문제 출처 www.acmicpc.net/problem/1744

1744번: 수 묶기