백준 11286번: 절댓값 힙(우선순위 큐)

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

11286번: 절댓값 힙

 

 

1. 코드 구현 

import sys
import heapq

n = int(sys.stdin.readline())
h = []

for _ in range(n):
    data = int(sys.stdin.readline())
    if data != 0:
        heapq.heappush(h,(abs(data),data))
    else:
        if not h:
            print(0)
        else:
            print(heapq.heappop(h)[1])

 

2. 틀린 이유

set을 사용하려고 시도한 접근은 맞았는데 어떤 값을 넣느냐를 잘못 선택했다.

heap에 절대값이 같고 부호반대인 원소가 들어있을 경우 (절대값, 2)를 추가한다는 식으로 접근하였는데 그렇게 생각하니 코드가 너무 복잡해졌다. set을 떠올린 것까지는 좋았으나 set의 기능에 대해서는 미처 간과하고 있었다.

heap에 데이터를 heappush하는 경우, 작은 값이 먼저 heappop된다. 왜냐하면 heap은 minHeap의 특성을 따르기 때문이다. 그런데 이때 set처리를 하여 원소를 넣어주면 set에 들어있는 원소 번호 순대로 정렬된다.

다시말해, set 형태로 heap에 (1,2) (0,3) (5,0) 을 넣어준다면 데이터는 첫번째 원소를 기준으로 먼저 정렬되고 첫번째 원소가 같다면 두번째 원소를 기준으로 정렬될 것이다. 따라서 (0,3) (1,2) (5,0)과 같은 순서로 데이터가 정렬된다. 여기서 heappop을 하면 당연히 (0,3)이 먼저 빠져나올 것이다. 따라서 이 문제에서는 절대값을 맨앞에 넣어 일단 데이터가 순서대로 정렬되고 두번째에 원래 값(음수나 양수)를 집어넣으면 당연히 절대값이 작은 순으로 정렬되게 세팅할 수 있다. 

 

문제에서 나와있듯이

1. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

 라는 부분을 보면 어떻게 처리해야 할지 정보를 대놓고 주고 있다. 첫째 글을 잘 읽고 먼저 명료한 컨셉을 잡고 코드를 작성하는 것이 가장 중요하다는 생각이 들었다.