[백준 11286] 절대값 힙 - python (solved.ac - 실버 1)

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

11286번: 절댓값 힙

풀이

문제를 보았을때 알수있는 힌트

문제를 전체적으로 읽고 예제 입력, 출력을 보고 이해하고 풀 수 있었던 문제이다. 

단순하게 푼다면 정렬을 하면서 풀수있겠지만, 그렇게 푼다면 정렬할때마다 시간이 소요되기에 시간초과가 나올것이다.

그렇기에 값을 넣거나 뺄때 바로 정렬이 되는 heap을 사용하면 해결할수 있는 문제이다.

 

여기서 약간 문제를 꼬았는데 바로 절대값을 넣어서 조금 어렵게 만들었다.

이건 단순하게 절대값도 리스트에 추가 시켜놓으면 해결할수 있었다.

예를 들어 -1의 값을 heap에 넣는다면 [절대값(-1),-1] =>[1,-1] 이렇게 집어 넣는다.

heap에서 자동을 작은 것부터 정렬이 되기 때문에 리스트의 처음인 1을 먼저 보고 정렬할것이고 다음으로 -1을 보고 다시 정렬할 것이다.

또한 함정으로 heap안에 아무것도 없는 경우 0이 출력되게 코드를 구현하면 끝이난다.

import sys
import heapq
input = sys.stdin.readline

h=[]
n = int(input())

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

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon11286.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리