leetcode: Maximum Frequency Stack

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

두가지 자료구조를 사용한다.

• frequency: (key, value) -> 값 key에 대한 빈도수 value를 저장한 자료구조
• frequencyValueStack: (key, stack) -> 빈도수 key에 대해 값 stack을 저장한 자료구조
• maxfrequency: 가장 많은 빈도수를 저장

import java.util.*;
class FreqStack {
	Map<Integer, Integer> frequency;
	Map<Integer, Stack<Integer>> frequencyValueStack;
	int maxfreq;

	public FreqStack() {
		frequency = new HashMap<Integer, Integer>();
		frequencyValueStack = new HashMap<Integer, Stack<Integer>>();
		maxfreq = 0;
	}

	public void push(int x) {
		int xFrequency = frequency.getOrDefault(x, 0) + 1;
		frequency.put(x, xFrequency);
		if (xFrequency > maxfreq) {
			maxfreq = xFrequency;
		}

		/*
		 * implement a multi-value map, Map<K,Collection<V>>, 
		 * supporting multiple values per key: 
		 * map.computeIfAbsent(key, k -> new HashSet<V>()).add(v);
		 */
		frequencyValueStack.computeIfAbsent(xFrequency, stack -> new Stack<Integer>()).push(x);
	}

	public int pop() {
		int x = frequencyValueStack.get(maxfreq).pop();
		
		frequency.put(x, frequency.get(x) - 1);
		if (frequencyValueStack.get(maxfreq).size() == 0) {
			maxfreq--;
		}
		return x;
	}
}