백준 11286번 절댓값 힙

백준 11286번 절댓값 힙 문제이다. 

 

문제는 다음과 같다.

요약해보면 첫번째로 몇번 입력받을것인지 N을 입력 받고 N번 입력을 받는다.

숫자가 0이 아닌 수가 나오면 배열에 저장하며

0이 나온 경우는 배열에서 절댓값이 가장 작은수, 절댓값이 같다면 원래의 값이 작은 수를 출력하는 문제이다. 

 

처음엔 그냥 배열을 만들고 -값에 대한 처리는 -1인 경우 0.5, -2인경우 1.5 이렇게 +0.5를 한 후 절댓값을 구해서 동일한 양수값보다 조금 작게 만들어 정렬을 했을때 -값이 먼저 출력 되도록 했다.

 

하지만. 배열을 사용하고 sort()함수를 사용해서 그런지 시간초과가 발생했다. 

 

찾아보니 heapq를 통해 우선순위 큐를 구현할 수 있었다. 

이 heapq를 사용하면 입출력을 하면서 바로 대소비교되어 들어가기 때문에 정렬이 필요 없으며 우선순위도 넣어줄수 있다.

하지만 우선순위는 내가 처음에 생각한 방식을 사용해서 구현했다. 

 

코드는 다음과 같다. 

import sys
import heapq

n = int(sys.stdin.readline().strip())
arr = []
for i in range(n):

    ins = sys.stdin.readline().strip()
    ins = int(ins)
    if ins == 0:
        if len(arr) == 0:
            print(0)
        elif type(arr[0]) == float:
            print(int(-(arr[0]+0.5)))
            heapq.heappop(arr)
        else:
            print(arr[0])
            heapq.heappop(arr)
    elif ins < 0:
        heapq.heappush(arr, abs(ins+0.5))
    else:
        heapq.heappush(arr, ins)

 

sort() 함수 하나만 해도 시간을 많이 잡아먹는것 같다. 

0.5를 더하여 우선순위를 주는 방식이 아닌 heapq에 있는 기능을 활용해도 될 것 같다. 

 

성공!