99클럽 코테 스터디 10일차 TIL + 힙(Heap)

[오늘의 학습 키워드 및 문제]
- 프로그래머스의 "이중우선순위큐" 문제를 풀었다.
- 어제와 마찬가지로 힙(Heap)을 이용해 푸는 문제였다.
- 문제 자체는 어렵지 않았는데, 힙 사용할 때 주의해야 할 점을 배울 수 있었다.

[나의 코드]

import heapq

def solution(operations):
    answer = []
    
    for operation in operations:
        if operation.split()[0] == 'I':
            heapq.heappush(answer, int(operation.split()[1]))
        else:
            if answer:
                if operation.split()[1] == "1":
                    answer.remove(max(answer))
                else:
                    heapq.heappop(answer)
    
    if answer:
        return [max(answer), min(answer)]
    else:
        return [0, 0]

문제 자체는 어렵지 않으므로 누구나 코드는 쉽게 짤 수 있었을 것이다.
하나 간과하지 못한 게 있었다.

최소 힙에서 루트 노드는 항상 최소값을 보장하지만, 마지막 원소는 최댓값을 보장하지 않는다.

 

• 구조적 위치: 힙의 마지막 원소는 트리의 구조적 특성상 마지막 레벨의 오른쪽 끝에 위치한다. 이 위치는 삽입 순서와 완전 이진트리 구조에 의해 결정된다.
• 정렬 순서: 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같은 값이지만, 이는 전체 트리에서의 전역적인 최댓값을 의미하지 않는다. 마지막 원소는 삽입된 순서에 따라 트리의 맨 마지막에 위치하므로, 최댓값이 아니며 단지 부모 노드보다 큰 값이라는 보장만 있다.

 

import heapq

# 힙에 숫자 삽입
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 15)
heapq.heappush(heap, 30)
heapq.heappush(heap, 50)
heapq.heappush(heap, 40)

print("힙 상태:", heap)

# 힙 상태: [10, 20, 15, 30, 50, 40]

위의 보기에서 볼 수 있듯이 최댓값인 50이 늘 마지막 원소라는 것을 보장하지 않는다.

그렇기 때문에 단순히 pop() 연산이나, 배열의 인덱스로 값을 접근하려 했다면 테스트를 통과하지 못했을 것이다.
그래서 최댓값을 구할 땐 max()를 써야 한다.

[오늘의 회고]
- 맨날 pop() 쓰다가 remove() 쓰려니 기억이 안 났다. ㅋ
- 힙이 최댓값을 보장하지 않는다는 중요한 사실을 공부했다. 잊지 말도록 하자. 
- 안 물어봤겠지만 오늘은 김도향 아저씨의 '외인구단'을 들으며 풀었다. 끝!