https://www.acmicpc.net/problem/11286
11286번: 절댓값 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
파이썬으로 heap문제를 풀려면 heapq라는 모듈을 알아야 한다.
https://solution-is-here.tistory.com/114
백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열
solution-is-here.tistory.com
위 링크를 보고 오면 heapq에 대해 쉽게 이해하실 수 있습니다.
heapq를 이해해야 문제를 풀수 있기 때문에 꼭 보시길 추천합니다.
문제를 보면 다른 힙 문제들과 다른 점을 찾을 수 있습니다.
바로 힙을 제거할때 절댓값이 가장 작은 값을 출력하고 절댓값이 가장 작은 값이 여러 개 일 때는 가장 작은 수를 출력하는 것입니다. 이를 해결하기 위해서는 heappush함수를 잘 사용해야 합니다.
|
1
|
heapq.heappush(heap,(abs(x),x))
|
cs |
원래는 heappush를 하고 리스트 이름과 변수 하나만 입력 했는데 이렇게 두 개를 넣으면 앞에 있는 절댓값을 기준으로 최소 힙에 숫자를 넣고 두 번째 숫자를 이용해서 절댓값이 똑같을 때 더 작은 숫자를 출력할 수 있게 해줍니다.
이것만 알면 이 문제는 정말 쉽게 풀 수 있다고 생각합니다.
출력할 때 절댓값이 아닌 절댓값 처리 하기 전 수가 궁금하면 첫 번째 인덱스를 출력하면 됩니다.
|
1
2
|
min = heapq.heappop(heap)
print(min[1])
|
cs |
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import sys
import heapq
heap = []
input = sys.stdin.readline
num = int(input())
for i in range(num):
x = int(input())
if x != 0:
heapq.heappush(heap,(abs(x),x))
else:
if len(heap) > 0:
min = heapq.heappop(heap)
print(min[1])
else:
print("0")
|
cs |