C++로 빈도 스택(FreqStack) 구현하기

이번 글에서는 FrequencyStack이라는 특별한 스택을 C++로 구성하는 방법을 알아보겠습니다. 이 스택은 다음 두 가지 연산을 지원합니다.

• append(x): 값 x를 스택에 추가(push)합니다.

• pop(): 스택에서 가장 자주 등장한(빈도가 가장 높은) 요소를 제거하고 반환합니다. 만약 빈도가 같은 요소가 여러 개 있다면, 그중 스택 최상단(top)에 가장 가까운, 즉 가장 나중에 삽입된 요소를 제거하고 반환합니다.

예를 들어 append를 통해 7, 9, 7, 9, 6, 7을 순서대로 삽입한 뒤 pop을 네 번 호출하면, 결과는 각각 7, 9, 7, 6이 됩니다.

문제 해결 접근 방법

이 문제의 핵심은 빈도별로 스택을 따로 관리하는 것입니다. 두 개의 해시맵과 최대 빈도를 추적하는 변수 하나만 있으면 모든 연산을 상수 시간에 처리할 수 있습니다.

• cnt: 각 요소의 등장 횟수를 저장하는 맵

• sts: 빈도를 키로 하고, 해당 빈도를 가진 요소들을 담는 스택을 값으로 갖는 맵

• maxFreq: 현재 스택 전체에서 가장 높은 빈도를 저장하는 변수 (초깃값 0)

append(x) 동작 과정

1. cnt[x]를 1 증가시킵니다.
2. maxFreq를 maxFreq와 cnt[x] 중 더 큰 값으로 갱신합니다.
3. x를 sts[cnt[x]] 스택에 삽입합니다.

pop() 동작 과정

1. maxKey := maxFreq로 설정합니다.
2. x := sts[maxKey]의 최상단(top) 요소를 가져옵니다.
3. sts[maxKey]에서 해당 요소를 제거(pop)합니다.
4. 만약 sts[maxKey]의 크기가 0이 되었다면:
   • sts에서 maxKey 키를 삭제합니다.
   • maxFreq를 1 감소시킵니다.
5. cnt[x]를 1 감소시킵니다.
6. x를 반환합니다.

이 방식이 잘 작동하는 이유는 간단합니다. 같은 빈도 그룹 안에서는 스택의 LIFO(Last-In-First-Out) 특성 덕분에 항상 가장 최근에 삽입된 요소가 top에 위치하게 되므로, "최고 빈도 + 최상단에 가장 가까운 요소"라는 조건을 자연스럽게 만족할 수 있습니다.

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#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 append(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.append(7);
    ob.append(9);
    ob.append(7);
    ob.append(9);
    ob.append(6);
    ob.append(7);
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
    cout << (ob.pop()) << endl;
}

입력

ob.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;

출력

7
9
7
6

복잡도 분석

append와 pop 연산 모두 해시맵 조회와 스택 push/pop만 사용하므로, 각 연산의 평균 시간 복잡도는 O(1)입니다. 공간 복잡도는 저장되는 요소의 총 개수 N에 비례하여 O(N)입니다.