[실버 I] 11286번. 절댓값 힙

 문제 

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

11286번: 절댓값 힙

 사용 언어 

Python3

 풀이 과정 

이 문제는 제목부터 힙을 사용하라고 암시하고 있다. 그런데 어떤 힙? 우선순위 큐!

따라서 구글링을 통해 heapq 구현법을 찾아서 아래까지는 쉽게 구현했다.

from heapq import heappop, heappush
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

N = int(input())
heap = []
for i in range(N):
    x = int(input())
    if x != 0:
        heappush(heap, x)
    else:
        if len(heap) == 0:
            print(f"0\n")
        else:
            print(f"{heappop(heap)[1]}\n")

0이 입력될 때마다 출력을 하기 때문에 출력 횟수가 많아 보여 stdout.write도 사용해주었고 heappush, heappop을 사용했다. 그런데 우선순위를 어떻게 적용해야 할 지 몰랐다가 블로그를 더 찾아보고 heappush의 두 번째 인자로 튜플을 넘겨면 된다는 사실을 깨달았다. 정확히는heap을 tuple로 구성했을 때 맨 앞 숫자만 가지고 정렬하므로 앞은 abs(절대값) 내장 함수를 써주고 두 번째는 원래 수를 써줌으로써 절댓값 정렬을 할 수 있게 하는 것이다.

 

그래서 그렇게 바꿔 제출했더니 맞았습니다!!

 

 제출 답안 

from heapq import heappop, heappush
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

N = int(input())
heap = []
for i in range(N):
    x = int(input())
    if x != 0:
        heappush(heap, (abs(x), x))
    else
        if len(heap) == 0:
            print(f"0\n")
        else:
            print(f"{heappop(heap)[1]}\n")

 

 공부한 내용 

PriorityQueue  vs  heqpq

파이썬에는 queue 모듈 안에 PriorityQueue라는 게 있고 heapq 모듈이 따로 있다.

따라서 이 두 가지 중에 뭐가 우선순위 큐라는 건지 헷갈렸는데, 결론적으로는 둘 다 우선순위 큐의 역할을 하지만 PriorityQueue는 Thread Safe하고 heapq는 Thread Non Safe하다고 한다.

 

당연히 Thread Safe하다는 것은 반드시 확인 절차를 거쳐야 하기 때문에 시간이 좀 더 걸리는데, 코딩테스트 문제를 풀 때는 Thread Safe할 필요가 없기 때문에 heapq를 쓰면 된다.

 

출처 : https://slowsure.tistory.com/130#--%--%EC%-B%A-%EC%A-%-C%--%EA%B-%BD%ED%--%--%ED%--%B-%EB%B-%B-%EA%B-%B- 

heappush, heappop, heapify

from heapq import heappop, heappush, heapify

파이썬에서 heap 생성은 그냥 빈 리스트를 생성해놓은 다음 heapq 모듈의 함수를 호출할 때마다 해당 리스트를 인자로 넘기면 된다. 다시 말해, 파이썬에서는 heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙이 되는 것이다.

 

힙에 원소를 추가할 때는 heappush를, 원소를 삭제할 때는 heappop을 사용하면 되고 둘다 O(log(n))의 시간복잡도를 가진다. 또 최솟값은 삭제하지 않고 리스트의 첫 번째 인덱스로도 접근할 수 있다.

 

또 이미 원소가 들어있는 리스트를 힙으로 만들려면 heapify 함수를 사용하면 된다. 리스트 내부의 원소들이 힙 구조로 재배치되며 최솟값이 0번째 인덱스에 위치하게 된다. 시간복잡도는 O(n)이며 주의할 점은 인자로 넘긴 리스트를 직접 변경하기 때문에 원본 리스트를 보존해야 하면 복제한 뒤에 인자로 넘겨야 한다는 것이다.

 

자세한 예시는 출처 블로그를 참조..!

 

출처: https://www.daleseo.com/python-heapq/