[python 구름] 0커플

📜 접근 방법

짝수인 n이 주어지며, n만큼 숫자가 들어오는데 짝이 아닐 경우 그 숫자를 더해야한다.

짝일 경우는 두 수를 더했을 시 0이 되어야한다.

 

우선순위 큐를 사용했고, 두 수를 더했을 때 0이면 결국 -k 와 k를 더했을 경우 0이 되기에

2개의 힙을 사용했다. (양수 넣는 힙과 음수 넣는 힙)

1. 입력받은 숫자들을 2개의 힙중 하나의 힙에 구분하여 넣는다.
2. 두개의 힙중 하나라도 비어지면 반복문 종료한다.
3. 짝이 아닐 경우 둘중 절대값이 작은 수를 res에 넣는다. (res는 짝이 없는 수들의 리스트) / 반복
4. 반복문이 종료되면 힙에 남는 값들을 전부 res에 넣어준다.
5. res에 들어간 값들의 합을 출력

 

✅ 정답 코드

 

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
minus_heap = []
plus_heap = []

# 양수와 음수 구별해서 넣기
for num in nums:
	if num > 0:
		heappush(plus_heap, num)
	else:
		heappush(minus_heap, -num)

res = []
while plus_heap and minus_heap:
	plus_n = heappop(plus_heap)
	minus_n = -heappop(minus_heap)
    
    # 짝이 아닐 경우(합이 0이 아닌 경우)
	if plus_n + minus_n != 0:
    	# 크기가 작은 수를 res에 넣기(짝이 없다는 것)
		if plus_n > abs(minus_n):
			res.append(minus_n)
			heappush(plus_heap, plus_n)
		else:
			res.append(plus_n)
			heappush(minus_heap, -minus_n)
            
# 힙에 남은 부분이 있을 경우
while plus_heap:
	res.append(heappop(plus_heap))
while minus_heap:
	res.append(-heappop(minus_heap))
			
print(sum(res))

 

💡알게 된점

처음엔 마지막 부분에서 짝이 맞지 않을 경우를 생각하지 못해서 오류가 났지만 다시 생각해보고 풀었다! 우선순위 큐를 나는 잘 사용하는듯하다.