힙_이중우선순위큐_Python
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어수신 탑(높이)
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
operationsreturn
입출력 예 설명
16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.
접근방법
heapq로 우선순위 큐를 구현한다.
빈 리스트에 heapq 메소드를 이용해 값을 관리하면 리스트는 heap 속성을 만족하게 된다(defult: min)
주어진 배열은 문자열이기에 명령과 값으로 분류 하고, min_heap이 int 요소를 갖게 하기 위해
str data => int data로 변환해준다.
최댓값을 삭제하는 경우
min_heap의 맨 마지막 인덱스가 최대값임을 이용
최솟값을 삭제하는 경우
heapq 는 기본적으로 min_heap이기에 heappop()로 가장 맨 앞의 인덱스값이 최솟값이다.
이때 data를 str 타입으로 사용하면 ㄱㄴㄷ 순과 같이 사전적 의미로 정렬 + 오름차순이 기본 값이 되기 때문에
-45 보다 -645가 더 큰값으로 인식하게 된다.
우선순위 큐에 데이터 삽입
만약 heap이 비어있는 경우를 고려해주었다.
2, 4, 6테스트 케이스 실패
import heapq
def solution(operations):
answer = []
min_heap = []
for value in operations:
order, data = value.split()
data = int(data)
if order == "D" and data == 1:
if min_heap:
# print('===555')
min_heap.pop(-1)
elif order == "D" and data == -1:
heapq.heappop(min_heap)
else:
heapq.heappush(min_heap, data)
if not min_heap:
return [0,0]
return min_heap[-1], min_heap[0]
개선
먼저 테스트 케이스 2, 4의 경우
질문을 참고하여 보니
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
라는 조건을 최댓값 삭제하는 경우만 적용해주었었다. 최솟값도 어짜피 삭제인데 말이다.
# 최댓값 삭제
if order == "D" and data == 1:
if min_heap:
min_heap.pop(-1)
# 최솟값 삭제
elif order == "D" and data == -1:
if min_heap:
heapq.heappop(min_heap)
개선_2
여기서 굉장히 중요한 내용을 학습할 수 있었다.
힙 구조는 우선순위가 높은 값이 루트 노드에 위치하게 되는 것을 보장하는 자료구조이다.
여기서는 어디에도 맨 마지막 리프 노드(요소)가 최댓값임을 보장하지 않는다는 것이었다.
힙 구조는 가장 우선순위가 높은 값이 먼저 pop 되는 것을 보장하는 자료구조이다.
pq[0]가 가장 우선순위가 높은 값(가장 작은값)인 것은 맞지만, 나머지 값에 대한 정렬은 보장하지 않는다는 의미이다. (프로그래머스 질문 답변: softmare님)
그냥 당연하게 맨 마지막 요소가 최댓값이지라는 생각을 가지고 있었었다.
힙 속성을 되새겨보면 (참고: 힙_1 :: muntari Log (tistory.com))
1. 형태 속성 : 힙은 완전 이진 트리여야 한다.
2. 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 작아야 한다.
import heapq
pq = []
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 4)
print(pq)
# [1, 2, 5, 3, 4]루트 노드 1은 최솟값임이 확실히 보장되나 모든 노드의 데이터는 자식 노드보다 작기만 하면 된다.
즉, 완전 이진 트리이면서 위 조건을 만족해야하기에 아래와 같은 트리 구조를 갖는다.
마지막 인덱스 4는 최댓값이라는 보장이 없다.
1
2 5
3 41. min_heap[-1]이 항상 최대값이라는 보장이 없다 =>
따라서 최댓값 삭제부분도 수정하고 리턴 값도 수정하였다.
import heapq
def solution(operations):
min_heap = []
for value in operations:
order, data = value.split()
data = int(data)
# 최댓값 삭제
if order == "D" and data == 1:
if min_heap:
max_value = max(min_heap)
min_heap.remove(max_value)
# 최솟값 삭제
elif order == "D" and data == -1:
if min_heap:
heapq.heappop(min_heap)
# 큐 데이터 삽입
else:
heapq.heappush(min_heap, data)
# heap이 비어있는 경우
if not min_heap:
return [0, 0]
return max(min_heap), min_heap[0]
시간복잡도
배열의 길이를 N이라 할때
힙은 N개의 노드와 lgN의 높이를 갖는다.
배열은 큐가 수행할 연산을 나타냄 => O(N)
split() => 주어진 문자열 모두 탐색 O(N)
max() => O(N)
remove() => O(N)
heappop() => O(lgN)
heappush() => O(lgN)
총시간복잡도는 O(N^2)?
우선순위 큐를 사용하는 이유는 삽입과 삭제를 O(N)이 아닌 O(lgN)의 효율로 사용하기 위함이다.
종합해볼때 N^2로 예상되는데.. 보시다시피 효율이 굉장히 좋다.
그냥 문제에서 원한 답을 찾아서 그런건지 모르겠다.
추후 질문 답변을 확인해보도록 하자