C++로 구현하는 최대 빈도 스택(Maximum Frequency Stack)

FreqStack이라는 이름의 특수한 스택을 구현해야 한다고 가정해 보겠습니다. 이 스택은 다음 두 가지 연산을 제공합니다.

push(x) — 정수 x를 스택에 삽입합니다.
pop() — 스택에서 가장 자주 등장한(빈도가 가장 높은) 요소를 제거하고 반환합니다. 만약 빈도가 같은 요소가 여러 개라면, 그중 스택의 최상단(top)에 가장 가까운 요소를 제거하여 반환합니다.

예를 들어, 7, 9, 7, 9, 6, 7 순서로 요소를 push한 후 pop을 네 번 호출하면 출력 결과는 각각 7, 9, 7, 6이 됩니다.

해결 접근 방식

이 문제는 두 개의 해시 맵과 하나의 변수를 활용하면 효율적으로 해결할 수 있습니다.

cnt — 각 요소의 출현 빈도를 저장하는 맵
sts — '빈도'를 키로 하고, 해당 빈도를 가진 요소들이 담긴 스택을 값으로 갖는 맵
maxFreq — 현재 스택 전체에서 가장 높은 빈도 값을 추적하는 변수

push(x)의 동작 과정

cnt[x]를 1 증가시킵니다.
maxFreq를 maxFreq와 cnt[x] 중 더 큰 값으로 갱신합니다.
x를 sts[cnt[x]]에 해당하는 스택에 삽입(push)합니다.

pop()의 동작 과정

maxKey를 maxFreq로 설정합니다.
sts[maxKey]의 최상단(top) 요소를 x에 저장합니다.
sts[maxKey]에서 해당 요소를 제거(pop)합니다.
만약 sts[maxKey]의 크기가 0이 되면, sts에서 maxKey 키를 삭제하고 maxFreq를 1 감소시킵니다.
cnt[x]를 1 감소시킵니다.
x를 반환합니다.

이 방식의 핵심은 빈도별로 별도의 스택을 유지하기 때문에, 같은 빈도 내에서는 나중에 들어온 요소가 먼저 꺼내져 '최상단에 가까운 요소 우선' 조건이 자연스럽게 충족된다는 점입니다. 또한 push와 pop 모두 O(1)의 시간 복잡도로 처리할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class FreqStack {
    public:
    unordered_map<int, int> cnt;
    unordered_map<int, stack<int>> sts;
    int maxFreq = 0;
    FreqStack() {
        maxFreq = 0;
        cnt.clear();
        sts.clear();
    }
    void push(int x) {
        cnt[x]++;
        maxFreq = max(maxFreq, cnt[x]);
        sts[cnt[x]].push(x);
    }
    int pop() {
        int maxKey = maxFreq;
        int x = sts[maxKey].top();
        sts[maxKey].pop();
        if(sts[maxKey].size() == 0){
            sts.erase(maxKey);
            maxFreq--;
        }
        cnt[x]--;
        return x;
    }
};
main(){
    FreqStack ob;
    ob.push(7);
    ob.push(9);
    ob.push(7);
    ob.push(9);
    ob.push(6);
    ob.push(7);
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
}

입력

요소 7, 9, 7, 9, 6, 7을 push한 후 pop()을 네 번 호출합니다.

출력