📜 접근 방법
짝수인 n이 주어지며, n만큼 숫자가 들어오는데 짝이 아닐 경우 그 숫자를 더해야한다.
짝일 경우는 두 수를 더했을 시 0이 되어야한다.
우선순위 큐를 사용했고, 두 수를 더했을 때 0이면 결국 -k 와 k를 더했을 경우 0이 되기에
2개의 힙을 사용했다. (양수 넣는 힙과 음수 넣는 힙)
- 입력받은 숫자들을 2개의 힙중 하나의 힙에 구분하여 넣는다.
- 두개의 힙중 하나라도 비어지면 반복문 종료한다.
- 짝이 아닐 경우 둘중 절대값이 작은 수를 res에 넣는다. (res는 짝이 없는 수들의 리스트) / 반복
- 반복문이 종료되면 힙에 남는 값들을 전부 res에 넣어준다.
- 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))
💡알게 된점
처음엔 마지막 부분에서 짝이 맞지 않을 경우를 생각하지 못해서 오류가 났지만 다시 생각해보고 풀었다! 우선순위 큐를 나는 잘 사용하는듯하다.
'코딩테스트 > Python' 카테고리의 다른 글
[python 구름] 제곱 암호 (0) | 2023.05.13 |
---|---|
[python 구름] 폭탄 구현하기 (2) | 2023.05.11 |
[python 구름] 대소문자 바꾸기 (0) | 2023.05.06 |
[python] 코딩테스트시 입력처리시 input 함수를 사용하지 않는 이유 (0) | 2023.05.06 |
[python 백준 2075] N번째 큰수 (0) | 2023.05.02 |