🚗현대인을 위한 3줄요약.
python에서는 우선순위 큐 알고리즘 중 하나인
heap을 라이브러리로 제공한다.
📌전체코드
우선 전체 코드는 다음과 같다.
import sys, heapq
input = sys.stdin.readline
numList = [] # heaqp은 빈 list로부터 시작된다.
case = int(input())
for i in range(case):
num = int(input())
if num == 0: # 입력받은 수가 0일 경우
if len(numList) == 0: # heaque이 비어있을 경우
print(0)
else:
# heappop()은 heaqp의 최상단 노드를 pop 하고 그 값을 반환한다.
# 튜플 형태의 원소가 저장되어 있기 때문에 튜플의 1번 index값(원래 값)을 출력한다.
print(heapq.heappop(numList)[1])
else:
# 튜플 형태로 numList에 원소를 삽입한다.
# 0번 자리에는 절댓값 비교를 위해 절댓값 num을, 1번 자리에는 본래 값(num)을 입력한다.
heapq.heappush(numList, (abs(num), num))해당 코드에서 면밀히 살펴볼 부분은 다음과 같다.
우선순위 큐: 우선순위가 높은 노드를 먼저 처리하는 큐의 형태heaqp: python에서 제공하는 우선순위 큐 알고리즘 중 하나.heappop & heappush: heaqp의 내장 메소드
각 키워드가 포함된 문단별로 나눠서 분석해보자
👉우선순위 큐
우선순위 큐 는 자료구조 알고리즘으로 먼저 들어오는 값이 아닌 우선순위가 높은 값을 최우선적으로 처리한다. 우선순위 큐에는 다양한 형태가 있으며 각각 쓰임이 다르다.
본 문제에서는 최대/최소값 처리에 용이한 heap 을 사용하고자 한다.
👉heaqp
heaqp 은 python에서 제공하는 heap 알고리즘으로 heap의 제어를 위한 다양한 메소드를 제공하기에 널리 쓰인다.
heaqp 을 알아보기 전에 heqp의 전신인 heap 알고리즘에 대해 먼저 짚고 넘어가도록 하겠다.
heap 은 다음과 같은 특징을 가지고 있다.
- heap은
완전 이진트리이다. 모든 노드에 저장된 값(우선순위)들은자식 노드들의 것보다 (우선순위가)크거나 같다.- 비교는 직접 연결된
부모,자식간에만 이루어 진다.
종합하면 heap은 우선순위가 높은 값을 최상위 노드 에 위치시킨다는 것을 알 수 있다.
따라서 위의 그림은 값이 낮을수록 우선순위가 높은 최소 heap 이라 볼 수 있겠다.
최소 heap 에서 새로운 값을 추가하는 경우 우선순위가 가장 낮다는 전제 하에 맨 끝 노드에 위치시킨다.
이후 부모 노드와의 비교를 진행, 우선순위에 의해 노드의 위치 변경이 요구될 경우 노드의 위치를 변경한다.
이와같은 과정을 위치가 맞을때 까지 반복한다.
노드 삭제의 경우 우선순위가 가장 높은 최상위 노드에 대해 pop을 진행하고 우선순위가 가장 낮은 최하위 노드를 빈자리에 채워 넣는다.
이후 leftchild와 rightchild간의 비교를 진행, 우선순위가 높은 노드와 자리를 변경하고 자리가 맞을때 까지 반복한다.
그래서 이 복잡하고 거추장 스러운걸 왜 쓰느냐?
배열, 연결리스트에 비해 월등히 빠르기 때문이다. 단적인 예로 배열을 이용해 우선순위 큐를 구현할 경우 비교연산시 배열 전체를 탐색 해야 하는 불상사가 벌어질 수 있다. 연결리스트 또한 마찬가지다.
게다가 파이썬에서는 heaqp 라이브러리를 제공하기 때문에 굳이 사용자가 직접 heap을 따로 구현하지 않아도 되기 때문이기도 하다.
👉heappop & heappush
heappop과 heappush는 heaqp라이브러리에서 제공하는 메소드이며 각각 큐에서의 pop, push의 역할을 한다. 이때 heap의 특성을 유지할 수 있게끔 각 노드의 비교연산을 자동으로 처리해준다.
import heapq
num = [5, 2, 1, 4, 3]
hq = []
for i in range(5):
heapq.heappush(hq, num[i])
# 실행 결과 : [1, 3, 2, 5, 4]num의 원소들을 heap hq에 heappush를 이용해 push하면 heap의 불변성 유지를 위해 다음과 같은 결과를 출력한다.
heaqp.heappop(hq)
# 실행 결과 : [2, 3, 4, 5]이상태에서 heappop을 실행할 경우 최상위 노드 1이 사라지고 노드의 재배치가 발생한다.
num = [(5,-5), (2, 2), (1, 1), (4, -4), (3, -3)]
hq = []
for i in range(5):
heapq.heappush(hq, num[i])
# 실행 결과 : [(1, 1), (3, -3), (2, 2), (5, -5), (4, -4)]heaqp은 또한 튜플 형태의 자료를 원소로 저장할 수 있다. 이 경우 튜플의 0번 index를 비교 기준으로 삼는다.
heaqp.heappop(hq)
# 실행 결과 : [(2, 2), (3, -3), (4, -4), (5, -5)]따라서 heappop을 진행하게 되면 튜플의 0번 index를 기준으로 노드의 재배치가 발생한다. 이를 이용해 본 문제의 절댓값을 이용한 최소 heap을 구현할 수 있다.
if num == 0: # 입력받은 수가 0일 경우
if len(numList) == 0: # heaque이 비어있을 경우
print(0)
else:
# heappop()은 heaqp의 최상단 노드를 pop 하고 그 값을 반환한다.
# 튜플 형태의 원소가 저장되어 있기 때문에 튜플의 1번 index값(원래 값)을 출력한다.
print(heapq.heappop(numList)[1])
else:
# 튜플 형태로 numList에 원소를 삽입한다.
# 0번 자리에는 절댓값 비교를 위해 절댓값 num을, 1번 자리에는 본래 값(num)을 입력한다.
heapq.heappush(numList, (abs(num), num))입력받은 숫자(=num)가 0이 아닐 경우 numList heap에 num의 절댓값과 num을 튜플의 형태로 삽입, num이 0이고 numList가 비어있지 않을 경우 최상위 노드 값(튜플)의 1번 index값을 출력한다.
만약 heap이 비어있을 경우 0을 출력한다. heappop은 heap이 비어있을 경우 index Error가 발생하기 때문에 이처럼 예외처리를 해준다.
📌다른 방법
import sys
import heapq
n = int(input())
q1 = [] # 음수를 넣을 큐
q2 = [] # 양수를 넣을 큐
for i in range(n):
a = int(sys.stdin.readline().rstrip())
if a < 0:
heapq.heappush(q1, -a) # 절대값이 작은게 앞에 와야 하므로
elif a > 0:
heapq.heappush(q2, a) # 양수이므로 그대로 최소힙으로 구현
else:
if not q1:
if not q2:
print(0)
else:
print(heapq.heappop(q2))
elif not q2:
print(-heapq.heappop(q1))
else:
tmp1 = -heapq.heappop(q1)
tmp2 = heapq.heappop(q2)
if abs(tmp1) > abs(tmp2):
print(tmp2)
heapq.heappush(q1, -tmp1)
else:
print(tmp1)
heapq.heappush(q2, tmp2)
# 출처 : https://hongcoding.tistory.com/77위의 코드는 튜플의 형태로 heap에 저장하지 않고 음수와 양수를 저장하는 각각의 heap을 선언, 비교 또한 각자 진행하는 형식의 코드이다. 우선순위 큐에 익숙하지 않다면 이런 방식도 괜찮다고 생각한다.
참고문서
- https://docs.python.org/ko/3.9/library/heapq.html ( 공식 문서 )
- https://chanhuiseok.github.io/posts/ds-4/ ( heap 알고리즘 자료 )
- https://hongcoding.tistory.com/77 ( 다른 해결과정 자료)
