우리가 FrequencyStack이라고 하는 하나의 스택을 구성하고 싶다고 가정하고, 우리의 FrequencyStack에는 두 가지 기능이 있습니다 -
-
append(x), 이것은 값 x를 스택에 추가하거나 푸시합니다.
-
pop(), 이것은 스택에서 가장 빈번한 요소를 제거하고 반환합니다. 빈도가 동일한 요소가 두 개 이상 있는 경우 스택의 맨 위에 가장 가까운 요소가 제거되고 반환됩니다.
따라서 입력이 7, 9, 7, 9, 6, 7과 같은 일부 요소를 추가한 다음 팝 작업을 네 번 수행하면 출력은 각각 7,9,7,6이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 맵 cnt 정의
-
하나의 맵 sts 정의
-
maxFreq :=0
-
함수 append()를 정의하면 x가 필요합니다.
-
(cnt[x]를 1씩 증가)
-
maxFreq :=maxFreq 및 cnt[x]의 최대값
-
x를 sts[cnt[x]]
에 삽입 -
함수 정의 pop()
-
maxKey :=maxFreq
-
x :=sts[maxKey]
의 최상위 요소 -
sts[maxKey]
에서 요소 삭제 -
sts[maxKey]의 크기가 0과 같으면 -
-
sts에서 maxKey 삭제
-
(maxFreq를 1만큼 감소)
-
-
(cnt[x]를 1만큼 감소)
-
x를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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