[LeetCode] #priorityQueue #heap #O(1) Maximum Frequency Stack

leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/587/week-4-february-22nd-february-28th/3655/

스택과 유사한 자료 구조인 FreqStack을 구현하십시오.

FreqStack은 두 가지 기능을 가지고 있습니다.

• push(int x), 스택에 정수 x를 집어넣습니다.
• pop(), 스택에서 가장 빈번하게 나타나는 요소를 제거한 뒤 반환합니다.
  • 가장 빈번하게 나타나는 요소가 두 개 이상인 경우 스택의 맨 위에서 가장 가까운 요소를 제거하고 반환합니다.

 

Example 1:

Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]

Output: [null,null,null,null,null,null,null,5,7,5,4]

Explanation: 6 번의 push 작업을 수행한 후 스택은 [5,7,5,7,4,5]입니다.
그다음 pop () -> 5가 가장 자주 발생하므로 5를 반환합니다. 스택은 [5,7,5,7,4]가됩니다.
pop ()-> 5와 7이 가장 빈번하지만 7이 맨 위에 가장 가깝기 때문에 7을 반환합니다. 스택은 [5,7,5,4]가됩니다.
pop ()-> 5를 반환합니다. 스택은 [5,7,4]가됩니다.
pop ()-> 4를 반환합니다. 스택은 [5,7]이됩니다.

Note:

• 스택에 삽입되는 x는 0 <= x <= 10^9 사이의 값입니다.
• 스택이 비어있는 경우 FreqStack.pop()은 호출되지 않습니다.
• 한 테스트 케이스에서 FreqStack.push는 10000 번을 넘지 않습니다.
• The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.
• 한 테스트 케이스에서 FreqStack.pop은 10000 번을 넘지 않습니다.
• 전체 테스트 케이스에서 FreqStack.push와 FreqStack.pop은 150000 번을 넘지 않습니다.

나의 풀이: 정렬

 

 

 

stack과 counter를 따로 유지하여 갯수를 세고, pop 할 때마다 sort를 통해 pop 할 대상을 찾도록 시도해 봤습니다.

class FreqStack:

    def __init__(self):
        self.stack = []
        self.counter = defaultdict(int)
        self.max = None

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.counter[x] += 1

    def pop(self) -> int:
        a = sorted([(i, self.counter[x], x)  for i, x in enumerate(self.stack[::-1])], key=lambda x: x[1], reverse=True)
        self.counter[a[0][2]] -= 1
        self.stack.pop(-a[0][0]-1)
        return a[0][2]

# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

정렬의 경우 시간 복잡도가 O(n log n)이며, 공간 복잡도는 O(n)입니다. 시간 초과.

정렬해서 인덱스 0 값만 사용하기 때문에 sorted를 max로 바꾸어 시간 복잡도를 O(n)으로 바꾸어봤지만 역시 시간 초과였습니다.

class FreqStack:

    def __init__(self):
        self.stack = []
        self.counter = defaultdict(lambda: [0, []])
        self.max = None

    def push(self, x: int) -> None:
        self.stack.append(x)
        self.counter[x][0] += 1
        self.counter[x][1].insert(0, len(self.stack) - 1)

    def pop(self) -> int:
        x = max(self.counter.items(), key=lambda x: x[1])[0]
        self.counter[x][0] -= 1
        i = self.counter[x][1].pop(0)
        return x

# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

나의 풀이: Max Heap

O(n)도 실패한다는 건, 풀이법의 시간 복잡도가 O(n)보다 작아야 한다는 의미로 해석할 수 있습니다. Priority Queue, Heap 자료구조를 사용하면 삽입, 삭제 시 시간 복잡도가 O(log n)이므로 Max Heap을 사용하여 시도해봅니다.

class FreqStack:

    def __init__(self):
        self.count = 0
        self.counter = defaultdict(int)
        self.stack = []

    def push(self, x: int) -> None:
        self.count -= 1
        self.counter[x] -= 1
        heapq.heappush(self.stack, (self.counter[x], self.count, x))
        
    def pop(self) -> int:
        x = heapq.heappop(self.stack)
        self.counter[x[2]] += 1
        return x[2]

# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

파이썬에서 heap은 단독 자료구조로 존재하지 않고, heapq 라이브러리를 사용하여 리스트 자료구조의 인덱스를 변경하여 사용합니다. 기본적인 heapq 함수들은 다음과 같습니다.

• heapq.heappush(heap, item): 힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.
• heapq.heappop(heap): 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다. 힙이 비어 있으면, IndexError가 발생합니다. 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.
• heapq.heapify(x): 리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

힙에 대한 자세한 내용은 다음 파이썬 표준 도큐멘트를 참고해주세요.

docs.python.org/ko/3.10/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.0a5 문서

파이썬에서 제공하는 heap은 min heap 형태이며, 이는 우리의 조건인 max heap에 부합하지 않습니다. 몇 가지 설정을 통해 min heap을 max heap으로 바꿀 수 있지만, 그보다는 count를 음수로 바꿔주는 편이 훨씬 간단합니다.