최대 주파수 스택

요소를 스택에 푸시하고 스택에서 가장 빈번한 요소를 팝하도록 스택과 유사한 데이터 구조를 설계합니다.
FreqStack 클래스를 구현합니다.

FreqStack() 빈 주파수 스택을 구성합니다.

void push(int val)는 정수val를 스택 맨 위로 푸시합니다.

int pop() 스택에서 가장 빈번한 요소를 제거하고 반환합니다.

가장 빈번한 요소에 대한 동률이 있는 경우 스택의 맨 위에 가장 가까운 요소가 제거되고 반환됩니다.

예 1:

입력
["FreqStack", "푸시", "푸시", "푸시", "푸시", "푸시", "푸시", "팝", "팝", "팝", "팝"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
산출
[널, 널, 널, 널, 널, 널, 널, 5, 7, 5, 4]

설명
FreqStack freqStack = 새로운 FreqStack();
freqStack.push(5);//스택은 [5]
freqStack.push(7);//스택은 [5,7]입니다.
freqStack.push(5);//스택은 [5,7,5]입니다.
freqStack.push(7);//스택은 [5,7,5,7]입니다.
freqStack.push(4);//스택은 [5,7,5,7,4]입니다.
freqStack.push(5);//스택은 [5,7,5,7,4,5]입니다.
freqStack.pop();//5가 가장 빈번하므로 5를 반환합니다. 스택은 [5,7,5,7,4]가 됩니다.
freqStack.pop();//7을 반환합니다. 5와 7이 가장 빈번하지만 7이 맨 위에 가장 가깝기 때문입니다. 스택은 [5,7,5,4]가 됩니다.
freqStack.pop();//5가 가장 빈번하므로 5를 반환합니다. 스택은 [5,7,4]가 됩니다.
freqStack.pop();//4, 5, 7이 가장 빈번하지만 4가 맨 위에 가장 가깝기 때문에 4를 반환합니다. 스택은 [5,7]이 됩니다.

제약:

0 <= val <= 109

최대 2 * 104 호출이 push 및 pop 로 이루어집니다.

pop 를 호출하기 전에 스택에 최소한 하나의 요소가 있어야 합니다.

해결책:

from collections import Counter

class FreqStack:

    def __init__(self):
        self.freq = Counter()
        self.maxfreq = 0
        self.freqgrp = {}

    def push(self, val: int) -> None:
        newfreq = self.freq[val] + 1
        self.freq[val] = newfreq
        self.maxfreq = max(self.maxfreq, newfreq)
        self.freqgrp[newfreq] = self.freqgrp.get(newfreq, []) + [val]

    def pop(self) -> int:
        val = self.freqgrp[self.maxfreq].pop()
        if len(self.freqgrp[self.maxfreq]) == 0:
            self.maxfreq -= 1
        self.freq[val] -= 1
        return val


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