Gidhub BE Developer

LeetCode : 895. Maximum Frequency Stack

2022-06-08
goodGid

895. Maximum Frequency Stack

Problem

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Example

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]

[1] Code (22. 06. 08) (x)

// Runtime: 48 ms
// Memory Usage: 75 MB
// Ref : https://leetcode.com/submissions/detail/716931012
class FreqStack {
    HashMap<Integer, Integer> map;
    List<List<Integer>> list;
    int maxCnt;

    public FreqStack() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    public void push(int val) {
        if (!map.containsKey(val)) {
            map.put(val, 0);
        }
        int cnt = map.get(val);
        if (list.size() < cnt + 1) {
            list.add(new ArrayList<>());
        }
        list.get(cnt).add(val);
        map.put(val, cnt + 1);
        maxCnt = Math.max(maxCnt, cnt);
    }

    public int pop() {
        List<Integer> targetList = list.get(maxCnt);
        int size = targetList.size();
        int item = targetList.get(size - 1);
        targetList.remove(size - 1);

        if (targetList.isEmpty()) {
            maxCnt--;
        }

        map.put(item, map.get(item) - 1);

        return item;
    }
}

Review

  • 10 ~ 15분 소요

  • Hard 문제인데 한 방에 맞춰서 기분이 좋다.


[2] Code (23. 03. 19)

Need to Retry -> 실력이 퇴화했나보다 못풀었다.

// Ref : https://leetcode.com/submissions/detail/918181349
  • 시도헸으나 못 풀었다.

Review

  • 이전에 풀었을 땐 아주 쉽게 풀었던 거 같은데

    지금은 왜 어려울까… ㅠ

    다시 복기를 해봐야겠다.


Reference


Recommend

Index