Maximum Frequency Stack | LeetCode 895

🤔 문제 : 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 5 7 4 5 순으로 값이 들어온다면, 아래 순서로 stack의 모습이 그려집니다.

이렇게 되면 가장 높은층에는 지금까지 중 가장 빈도가 높은 숫자들이 들어가 있으며,
각 층에서도 가장 마지막에 들어온 숫자는 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) ... } }