boj.kr/1744 수 묶기 (gold4) 파이썬 풀이

1. 0인 경우 0의 개수를 카운트

2. 1인 경우 출력 tot 값을 1 증감

3. 양수인 경우 양수 최대힙에 추가

4. 음수인 경우 음수 최소힙에 추가

5. 양수 최대힙의 길이가 1 이하일때 까지, heappop한 두 수를 곱해서 출력 tot 값에 추가

6. 양수 최대힙에 양수가 남은 경우 출력 tot 값에 추가

7. 음수 최소힙의 길이가 1 이하일 때까지, heappop한 두 수를 곱해서 출력 tot 값에 추가

8. 음수 최소힙에 음수가 남은 경우 , 0의 개수를 카운트하고

8.1. 0이 1개라도 있으면 출력 tot값에 0을 추가하고

8.2. 0이 1개도 없으면 음수를 출력 tot 값에 추가

9. tot 값을 출력

 

N = int(input())

import heapq as hq

nums1 = [] # 양수 최대힙
nums2 = [] # 음수 최소힙
cnt_0 = 0
tot = 0

for _ in range(N):
    num = int(input())
    if num == 0:
        cnt_0 += 1
    if num == 1:
        tot += 1
    if num > 1:
        hq.heappush(nums1, -num)
    if num < 0:
        hq.heappush(nums2, num)

while len(nums1) > 1:
    num1 = -hq.heappop(nums1)
    num2 = -hq.heappop(nums1)
    tot += (num1*num2)
if nums1:
    tot += -hq.heappop(nums1)

while len(nums2) > 1:
    num1 = hq.heappop(nums2)
    num2 = hq.heappop(nums2)
    tot += (num1 * num2)
if nums2:
    if cnt_0 > 0:
        cnt_0 -= 1
        tot += 0
    else:
        tot += hq.heappop(nums2)

print(tot)

 

heapq는 기본 최소힙으로 동작한다. 따라서 최대힙을 만드려면 부호를 바꾸어(-를 붙여) 추가하고 꺼낼때 부호를 바꾸어(-를 붙여) 꺼내면 된다.