🤔 문제 : Maximum Frequency Stack | LeetCode 895
문제 : https://leetcode.com/problems/maximum-frequency-stack/
문제에서 만들고자 하는 Frequncy Stack은
- 기존 stack과 같은 구조를 같지만
pop할 때 단순히 가장 위에 있는 원소가 아닌- 가장 많이 들어있는 원소들 중 가장 위에 있는 원소를 반환함
=> 각 원소가 몇 번 나왔는지를 효율적으로 count하고 caching할 방법이 필요함
💡 풀이
1. Pop할 때 Stack 내 모든 원소를 세어 가장 많이 나온 원소를 반환
처음에는 Time Limit Exceed 신경쓰지 않고, 가장 단순한 풀이로 풀어봅니다.
push는 기존 stack과 동일하고pop은 전체 stack을 돌며 각 원소의 갯수를 count하여 가장 많이 나온 원소 반환
var FreqStack = function() {
this.array = []; // stack
};
/**
* push operation은 기존 Stack과 같음
*/
FreqStack.prototype.push = function(val) {
this.array.push(val)
};
/**
* pop operation은 반환 전에 전체 array를 iteration하며 각 element가 몇 번 등장하는지 count 한 후
* 가장 많이 나온 element의 가장 마지막에 들어온 위치를 pop
*/
FreqStack.prototype.pop = function() {
var max = 0; // 가장 많이 나온 element의 빈도
var maxPosition = 0; // 가장 많이 나온 element의 마지막 position
const cache = [];
for(const index in this.array){
const i = this.array[index];
// i가 몇 번 나왔는지 count
if(!cache[i])
cache[i] = 1;
else cache[i]++;
// 가장 많이 나온 빈도보다 클 경우 max값 update
if(cache[i] >= max){
max = cache[i];
maxPosition = index;
}
}
const result = this.array[maxPosition];
this.array.splice(maxPosition, 1);
return result;
};Time Complexity
push:O(1)stack의 가장 top에 push
pop:O(N)stack 전체를 돌며 각 원소의 빈도를 count
Space Complexity
O(N)각 원소를 한번씩만 저장하면 됨
정답은 원하는대로 나오지만 (역시나..) TLE 입니다.
pop operation을 O(N)보다 빠르게 할 방법이 필요해 보이네요.
2. Double Stack 구조로 각 원소의 빈도 caching
각 원소가 몇번 나왔는지를 매번 count하지 않아도 되도록
효율적으로 저장할 수 있는 방법을 떠올려야 했는데요,
제가 고민한 형태는 아래와 같은 이중 stack입니다.
stack이 층 별로 나워진 형태인데, 각 N층의 stack은 N번째로 들어온 원소들끼리의 stack이라고 보면 됩니다.
(해당 원소의 빈도에 해당하는 층에 push)
[
[5, 7, 4], // 1층
[5, 7], // 2층
[5] // 3층
]예를들어 5 7 5 7 4 5 순으로 값이 들어온다면, 아래 순서로 stack의 모습이 그려집니다.
push(5) : 5가 들어온 적 없음 -> 1층에 push
[
[5] // 1층
]push(7) : 7이 들어온 적 없음 -> 1층에 push
[
[5, 7] // 1층
]push(5) : 5가 이미 하나 있음 -> 2층에 push
[
[5, 7], // 1층
[5] // 2층
]push(7): 7이 이미 하나 있음 -> 2층에 push
[
[5, 7], // 1층
[5, 7] // 2층
]push(4): 4가 들어온 적 없음 -> 1층에 push
[
[5, 7, 4], // 1층
[5, 7] // 2층
]push(5) : 5가 이미 두개 있음 -> 3층에 push
[
[5, 7, 4], // 1층
[5, 7], // 2층
[5] // 3층
]이렇게 되면 가장 높은층에는 지금까지 중 가장 빈도가 높은 숫자들이 들어가 있으며,
각 층에서도 가장 마지막에 들어온 숫자는 stack의 top에 있는 구조로 유지됩니다.
따라서 pop을 할 때는 가장 높은층의 stack에서 하나씩 Pop을 해주면 됩니다.
var FreqStack = function() {
this.doubleStack = []; // 어떤 숫자가 몇 번째에 나왔는지
/** ex)
* [, [1, 2, 5], [2, 1], [1]] => 1은 3번 2는 2번 5는 1번 나옴
**/
};
/**
* @param {number} val
* @return {void}
*/
FreqStack.prototype.push = function(val) {
for(var i=this.cache.length; i>0; i--){ // 가장 윗층부터 돌면서
if(this.cache[i] && this.cache[i].includes(val)){ // 그 층에 val이 있으면
if(this.cache[i+1]) this.cache[i+1].push(val) // 그 윗층에 val을 push
else this.cache[i+1] = [val]
return;
}
}
if(this.cache[1]) this.cache[1].push(val) // 모든층에 val이 없으면 1층에 push
else this.doubleStack[1] = [val]
return;
};
/**
* @return {number}
*/
FreqStack.prototype.pop = function() {
const maxFrequency = this.doubleStack.length-1;
const targetNum = this.doubleStack[maxFrequency].pop();
if(this.doubleStack[maxFrequency].length === 0) this.doubleStack.pop();
return targetNum;
};
Time Complexity
push:O(N)전체 stack을 돌며 해당 원소를 찾아야 함
pop:O(1)stack의 가장 위의 원소를 pop
Space Complexity
O(N)각 원소를 한번씩만 저장하면 됨
제출하니 통과는 되었는데요,
생각해보면 push할 때 stack을 iteration하며 몇번째 층에 나온적이 있는지 확인해야 하니 push operation의 TC는 여전히 O(N)이 되겠네요.
같은 원소가 여러번 반복해서 들어온다면 이 방법이 효율적이겠지만, 새로운 원소가 계속 들어온다 생각하면 Stack 전체를 iteration해야 하는 경우가 많아지므로 1번 풀이와 비슷한 속도가 될 수도 있겠습니다.
통과된 것을 보면 테스트케이스에
- 같은 원소를 여러번 push하는 경우가 많고
- Stack이 아주 클 때 pop을 하는 경우가 많아
push보다는 pop의 효율성이 중요하지 않았나 생각이 듭니다.
3. 2번풀이 push의 TC(Time Complexity)최적화
2번 풀이의 Push operation을 좀 더 최적화해보겠습니다.
Stack을 돌며 몇층에 push할지 정하는게 아니라, inFloor라는 이름의 cache를 사용하여 현재까지의 빈도를 따로 저장해두겠습니다.
push할 때는 inFloor[val]+1 층에 push하면 되겠지요
var FreqStack = function() {
this.doubleStack = []; // 어떤 숫자가 몇 번째에 나왔는지
/** ex)
* [, [1, 2, 5], [2, 1], [1]] => 1은 3번 2는 2번 5는 1번 나옴
**/
this.inFloor = []; // 각 element의 빈도
/** ex)
* [, 3, 2, , , 1] => 1은 3번 2는 2번 5는 1번 나옴
**/
};
FreqStack.prototype.push = function(val) {
if(!this.inFloor[val]) this.inFloor[val] = 0;
this.inFloor[val]++;
if(!this.doubleStack[this.inFloor[val]]) this.doubleStack[this.inFloor[val]] = []
this.doubleStack[this.inFloor[val]].push(val)
};
FreqStack.prototype.pop = function() {
const maxFrequency = this.doubleStack.length-1;
const targetNum = this.doubleStack[maxFrequency].pop();
this.inFloor[targetNum]--;
if(this.doubleStack[maxFrequency].length === 0) this.doubleStack.pop();
return targetNum;
};Time Complexity
push:O(1)전체 stack을 돌며 해당 원소를 찾아야 함
pop:O(1)stack의 가장 위의 원소를 pop
Space Complexity
O(N)각 원소를 한번씩만 저장하면 됨
📖 Learned
js로 푸는 알고리즘 문제 중 이렇게 클래스를 구현해내야 하는 문제는 생소해서, push와 pop함수를 어디에 작성해야하는지, 클래스 내의 변수는 어떻게 선언해야 하고, 함수 내에서 그 변수를 어떻게 접근해야 하는지 좀 헤맸습니다..;;
위에 풀이처럼 .prototype.함수 로 작성해도 되고
아래 처럼도 구현 가능합니다
function FreqStack() {
let m =[];
return {
push,
pop
}
function push(x) {
m.push(x) ...
}
function pop() {
m.pop(x) ...
}
}