Notion에서 작성한 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] Kth Largest Element in a Stream

[Kth Largest Element in a Stream]

개인적으로 오늘의 비기너, 미들러, 챌린저 문제 중 가장 어려웠다. 왜 어렵게 느꼈는지 돌아보면, ① 반복적으로 $K$번째로 큰 원소를 효율적으로 return시킬 발상이 잘 떠오르지 않았고, ② 클래스 사용이 미숙했다.

Solution. $O(\lg n)$ for each add()

from heapq import *

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.heap = nums
        self.k = k

        heapify(self.heap)
        while self.heap and len(self.heap) > k:
            heappop(self.heap)

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heappush(self.heap, val)
            return self.heap[0]

        if val <= self.heap[0]:
            return self.heap[0]

        heappushpop(self.heap, val)        
        return self.heap[0]

• 반복적으로 $K$번째로 큰 원소를 return한다 ⇒ $K$개의 원소를 갖는 최소 힙을 구성하고 나면, 이 힙의 최솟값이 곧 $K$번째로 큰 원소이다.
  • 힙의 크기를 $K$개로 계속 유지시켜주어야 하는 것이 포인트이다.
    • 새로 add() 하려는 값이 힙의 최솟값보다 작거나 같다는 것은, $K$번째로 큰 원소가 바뀌지 않는다는 의미이므로 그대로 힙의 최솟값을 return한다.
    • 새로 add() 하려는 값이 힙의 최솟값보다 크다는 것은 $K$번째로 큰 원소가 바뀐다는 의미이므로, 힙에서 최솟값을 pop한 다음 push해 준다. (이 경우에서는 push를 먼저 하고 pop을 해도 상관없으므로, heappushpop을 이용했다.)
    • 하지만 놓쳤던 부분이 있었다. 처음 힙을 구성할 때 $K$개보다 적은 nums로 힙이 구성되는 경우였다. Constraints에서 $K$번째 원소를 찾을 때 $K$개의 원소가 있다는 것이 보장된다고 했는데 왜 그런 건지 고민했는데, push를 해야 $K$개가 되는 경우가 문제였다. 항상 경계 조건에 유의해야 겠다.

---

[Middler] 이중우선순위큐

[이중우선순위큐]

Solution. Heap $O(2n \lg n)$

from heapq import *
from collections import defaultdict

def solution(operations):
    def sync_remove(heap, n):
        while heap and not log[-n*heap[0]]: heappop(heap)
        if heap: log[-n*heappop(heap)] -= 1

    mx = []
    mn = []
    log = defaultdict(int)
    
    for o in operatios:
        c, n = o.split()
        n = int(n)

        if c == 'I':
            heappush(mx, -n)
            heappush(mn, n)
            log[n] += 1

        else: sync_remove(mx if n==1 else mn, n)
    
    while mx and not log[-mx[0]]: heappop(mx)
    while mn and not log[mn[0]]: heappop(mn)

    return [-mx[0], mn[0]] if mx else [0, 0]

• heapq를 이용하여 최솟값과 최댓값을 한 번에 관리할 수는 없다. 따라서, min-heap과 max-heap을 따로 관리하여야 한다.

• 여기서, "D 1" 로 최댓값을 삭제하는 상황을 생각해 보자. max-heap에서 heappop()을 해 주고, min-heap에서는 어떻게 해야 할까?

  • min-heap에서 heappop()을 할 경우 최솟값이 삭제되는 것이고, ( X )
  • remove()를 이용할 경우 매 삭제마다 $O(n)$이 소요된다. ( X )

• → 힙에서 삭제 연산을 진행할 때,삭제 과정의 동기화를 위해 무슨 원소를 삭제했었는지 기록을 남겨놓고,

  • 삭제하려는 최댓값 또는 최솟값이 다른 힙에서 이미 삭제된 값은 아닌지 확인한 다음, 이미 삭제된 값이라면 $O(\lg n)$이 소요되는 heappop()을 이용하여 유효한 값이 나올 때까지 삭제함으로써 두 힙을 동기화시켜준다.

• 이를 위해 값을 찾는 데 Amortized $O(1)$이 소요되는 dictionary를 이용했다.

• I $n$ (삽입)

  • min-heap에 그대로 push한다.
  • max-heap에는 $-n$으로 push한다.
  • 삽입을 기록해 놓는다. 해당 원소가 몇 개 존재하는지에 해당하는 dictionary를 갱신한다. (삽입되었다는 의미로 $n$의 개수를 1 증가시켜준다.)

• “D 1” (최댓값 삭제)

  • max-heap의 최댓값이 유효한 값인지(min-heap에서 이미 삭제된 값은 아닌지) 확인하고, 최댓값이 유효한 값일 때까지 pop한다. 이 때, max-heap에는 $-n$으로 push되었음에 유의해야 한다.
  • 유효한 최댓값이 존재한다면 pop한 뒤 dictionary를 갱신한다. (삭제되었다는 의미로 $n$의 개수를 1 빼준다.)

• “D -1” (최솟값 삭제)

  • min-heap의 최솟값이 유효한 값인지(max-heap에서 이미 삭제된 값은 아닌지) 확인하고, 최솟값이 유효한 값일 때까지 pop한다.
  • 유효한 최솟값이 존재한다면 pop한 뒤 dictionary를 갱신한다. (삭제되었다는 의미로 $n$의 개수를 1 빼준다.)

• return

  • return 전 어느 한 heap은 유효하지 않을 수 있다(삭제 과정이 동기화되지 않았을 수 있다).
  • max-heap의 최댓값이 유효한 값이 나올 때까지 계속해서 pop하고, min-heap의 최솟값이 유효한 값이 나올 때까지 계속해서 pop하여 동기화해준다.

---

[Challenger] 최대 힙

[최대 힙]

• Priority Queue의 기본 문제 격인 이 문제가 챌린저 문제로 나왔다는 것은 아마 직접 구현해보라는 뜻일 것 같다. 꼭 직접 구현해 봐야 겠다 🥲

Solution 1. $O(n \lg n)$

from heapq import *

heap = []
for _ in range(int(input())):
    x = int(input())
    if x: heappush(heap, -x)
    else: print(-heappop(heap) if heap else 0)

---