코테준비/백준

[백준] 11286번: 절대값 힙 - Python

예찬예찬 2025. 6. 8. 14:49
728x90
반응형

링크: https://www.acmicpc.net/problem/11286

아이디어

  • 입력을 받을 때마다 자동정렬이 되는 힙 자료구조를 사용하자
  • 파이썬의 heapq를 사용
  • 튜플 자료형을 사용하여 우선순위로 사용할 절대값을 앞에 뒤에는 입력받은 값을 저장한다.
  • 이러면 절대값을 기준으로 자동 정렬이 되어 음수인지 양수인지도 알 수 있게된다.

구현

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []
for i in range(N):
    tmp = int(input())
    if tmp != 0:
        heapq.heappush(heap, (abs(tmp), tmp))
    else:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap)[1])

마무리

이 문제의 키워드는 힙에 넣을 때 튜플로 넣어 원하는 우선순위로 값을 저장 하도록 하는게 핵심이였던 거 같다.

한번에 이 방법이 떠오르지 않아 서치를 통해 알게 된게 좀 아쉽다. 많이 풀면 생각의 폭이 넓어지겠지..

728x90
반응형