https://leetcode.com/problems/maximum-frequency-stack/description/
Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
Implement the FreqStack class:
- FreqStack() constructs an empty frequency stack.
- void push(int val) pushes an integer val onto the top of the stack.
- int pop() removes and returns the most frequent element in the stack.
- If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.
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
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
Constraints:
- 0 <= val <= 109
- At most 2 * 104 calls will be made to push and pop.
- It is guaranteed that there will be at least one element in the stack before calling pop.
코딩을 하면서 특정 Customized Container에 대한 구현을 할 수 있는 능력을 기르는 것은 필수다.
Queue, Stack, Heap 이런것들을 Array / Linked List로 다 구현해보았으니 이렇게 Customized 된 Container의 구현도 한 번쯤은 해보자.
특이점은 Tie 상황일 땐, Stack Top에 가장 가까운 Element를 pop해야한다는 것이다.
1. Python
Python으로 하면 그냥 기본 list method를 써버리면 쉽게 풀 수 있을 거 같다.
또 적절한 Case는 푸는 코드를 만들었는데 그놈의 Time limit .. ㅠㅠ
class FreqStack:
def __init__(self):
self.lst = []
self.dic = {}
def push(self, val: int) -> None:
self.lst.append(val)
if val not in self.dic :
self.dic[val] = 1
else : self.dic[val] += 1
def pop(self) -> int:
# Ignore Empty Case(Constraint)
# Find most freq case
cnt = 0
for x in self.dic :
cnt = max(cnt,self.dic[x])
# Check Tie
target = []
for x in self.dic :
if self.dic[x] == cnt:
target.append(x)
# DO pop
for i in range(len(self.lst)-1,-1,-1):
if self.lst[i] in target:
ans = self.lst.pop(i)
self.dic[ans] -= 1
return ans
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
시간 복잡도 분석
|
시간도 저 정도면 괜찮은 거 아닌가-_-;;
모범답안 O(1)
class FreqStack:
def __init__(self):
self.freq = {} # 각 값의 빈도를 저장
self.group = {} # 빈도별 스택
self.max_freq = 0 # 현재 최대 빈도
def push(self, val: int) -> None:
# 값의 빈도 증가
if val not in self.freq:
self.freq[val] = 0
self.freq[val] += 1
freq = self.freq[val]
# 최대 빈도 갱신
if freq > self.max_freq:
self.max_freq = freq
# 해당 빈도의 그룹에 값 추가
if freq not in self.group:
self.group[freq] = []
self.group[freq].append(val)
def pop(self) -> int:
# 최대 빈도에서 값을 꺼냄
val = self.group[self.max_freq].pop()
# 그룹이 비었다면 max_freq 감소
if not self.group[self.max_freq]:
del self.group[self.max_freq]
self.max_freq -= 1
# 해당 값의 빈도 감소
self.freq[val] -= 1
if self.freq[val] == 0:
del self.freq[val]
return val
내 뜻대로 풀어본 코드
class FreqStack:
def __init__(self):
self.freq = {}
self.stack = {}
self.max_val = 0
def push(self, val: int) -> None:
if val not in self.freq:
self.freq[val] = 1
else : self.freq[val] += 1
val_freq = self.freq[val]
self.max_val = max(self.max_val,val_freq)
if val_freq not in self.stack:
self.stack[val_freq] = [val]
else : self.stack[val_freq].append(val)
def pop(self) -> int:
ans = self.stack[self.max_val].pop()
if not self.stack[self.max_val]:
del self.stack[self.max_val]
self.max_val -=1
self.freq[ans] -= 1
if self.freq[ans] == 0: del self.freq[ans]
return ans
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()
2. C/C++로도 풀어보자
솔직히 이걸 C로 풀기엔 Dictionary가 없어서 너무 빡세고, C++로 가보자.. map이 있으니까..!
C 코드는 아래와 같긴한데 넘 어거지스럽다;;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Hashmap node for frequency mapping
typedef struct FreqNode {
int key;
int value;
struct FreqNode* next;
} FreqNode;
// Linked list node for group stack
typedef struct Node {
int value;
struct Node* next;
} Node;
// Main FreqStack structure
typedef struct {
FreqNode** freqMap; // Hashmap for frequency mapping
Node** group; // Array of stacks for frequency groups
int maxFreq; // Current maximum frequency
int capacity; // Initial capacity for group array
} FreqStack;
// Hash function for frequency map
int hashFunc(int key, int capacity) {
return key % capacity;
}
// Create frequency map
FreqNode* createFreqNode(int key, int value) {
FreqNode* newNode = (FreqNode*)malloc(sizeof(FreqNode));
newNode->key = key;
newNode->value = value;
newNode->next = NULL;
return newNode;
}
// Search key in frequency map
FreqNode* freqMapSearch(FreqNode** map, int key, int capacity) {
int hashIndex = hashFunc(key, capacity);
FreqNode* current = map[hashIndex];
while (current) {
if (current->key == key)
return current;
current = current->next;
}
return NULL;
}
// Insert or update key in frequency map
void freqMapInsert(FreqNode** map, int key, int value, int capacity) {
int hashIndex = hashFunc(key, capacity);
FreqNode* current = map[hashIndex];
FreqNode* existing = freqMapSearch(map, key, capacity);
if (existing) {
existing->value = value;
} else {
FreqNode* newNode = createFreqNode(key, value);
newNode->next = map[hashIndex];
map[hashIndex] = newNode;
}
}
// Linked list stack push
void stackPush(Node** stack, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->next = *stack;
*stack = newNode;
}
// Linked list stack pop
int stackPop(Node** stack) {
if (*stack == NULL) {
return -1;
}
Node* topNode = *stack;
int value = topNode->value;
*stack = topNode->next;
free(topNode);
return value;
}
// Free stack
void freeStack(Node* stack) {
while (stack) {
Node* temp = stack;
stack = stack->next;
free(temp);
}
}
// Create FreqStack
FreqStack* freqStackCreate() {
FreqStack* obj = (FreqStack*)malloc(sizeof(FreqStack));
obj->capacity = 10000; // Initial capacity for hashmap and group
obj->freqMap = (FreqNode**)calloc(obj->capacity, sizeof(FreqNode*));
obj->group = (Node**)calloc(obj->capacity, sizeof(Node*));
obj->maxFreq = 0;
return obj;
}
// Push value into FreqStack
void freqStackPush(FreqStack* obj, int val) {
// Update frequency in freqMap
FreqNode* existing = freqMapSearch(obj->freqMap, val, obj->capacity);
int freq = existing ? existing->value + 1 : 1;
freqMapInsert(obj->freqMap, val, freq, obj->capacity);
// Update maxFreq
if (freq > obj->maxFreq) {
obj->maxFreq = freq;
}
// Push value to the corresponding frequency group stack
if (obj->group[freq] == NULL) {
obj->group[freq] = NULL; // Initialize stack if not exists
}
stackPush(&obj->group[freq], val);
}
// Pop the most frequent value from FreqStack
int freqStackPop(FreqStack* obj) {
// Pop from the maxFreq stack
int val = stackPop(&obj->group[obj->maxFreq]);
if (val == -1) {
return -1; // Should not happen based on constraints
}
// Update frequency in freqMap
FreqNode* existing = freqMapSearch(obj->freqMap, val, obj->capacity);
if (existing) {
existing->value -= 1;
}
// If maxFreq stack is empty, decrement maxFreq
if (obj->group[obj->maxFreq] == NULL) {
obj->maxFreq--;
}
return val;
}
// Free FreqStack
void freqStackFree(FreqStack* obj) {
// Free all frequency map nodes
for (int i = 0; i < obj->capacity; i++) {
FreqNode* current = obj->freqMap[i];
while (current) {
FreqNode* temp = current;
current = current->next;
free(temp);
}
}
free(obj->freqMap);
// Free all stacks
for (int i = 0; i <= obj->maxFreq; i++) {
freeStack(obj->group[i]);
}
free(obj->group);
// Free the main object
free(obj);
}
이번엔 C++로 풀어보기 진또배기!
C++!
class FreqStack {
public:
map<int,stack<int>> s;
map<int,int> f;
int max_freq;
FreqStack() : max_freq(0){}
void push(int val) {
// find val in f-map
if(auto it=f.find(val); it == f.end()) f[val] = 0;
f[val]++;
//max_freq update
max_freq = max(max_freq,f[val]);
// s-map update
if(auto it=s.find(f[val]); it == s.end()) s[f[val]] = {};
s[f[val]].push(val);
return;
}
int pop() {
int ans = s[max_freq].top();
s[max_freq].pop();
if(s[max_freq].empty()){
// delete s[max_freq]; //has to do it? --> Nope
max_freq--;
}
f[ans]--;
return ans;
}
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/
간결버전은 아래와 같다.
class FreqStack {
public:
map<int, stack<int>> s; // 빈도별 스택
map<int, int> f; // 각 값의 빈도
int max_freq = 0; // 최대 빈도
void push(int val) {
max_freq = max(max_freq, ++f[val]);
s[f[val]].push(val);
}
int pop() {
int val = s[max_freq].top();
s[max_freq].pop();
if (s[max_freq].empty()) max_freq--;
f[val]--;
return val;
}
};'Coding_Practice' 카테고리의 다른 글
| Minimum Cost For Tickets(Array,Dynamic Programming) (0) | 2024.12.31 |
|---|---|
| Count Ways To Build Good Strings(Dynamic Programming) (0) | 2024.12.30 |
| Best Sightseeing Pair(Array,Dynamic Programming) (1) | 2024.12.27 |
| Target Sum(Array,Dynamic Programming,Backtracking) (2) | 2024.12.26 |
| Find Minimum Diameter After Merging Two Trees(Tree,Depth-First Search,Breadth-First Search,Graph) (0) | 2024.12.24 |