[leetcode] Maximum Frequency Stack

문제

https://leetcode.com/problems/maximum-frequency-stack/submissions/

Maximum Frequency Stack - LeetCode

내 풀이

import java.util.*;

public class FreqStack {

  public class Data {

    public int number;
    public int nowCount;
    public int latest;

    public Data(int number, int nowCount, int latest) {
      this.number = number;
      this.nowCount = nowCount;
      this.latest = latest;
    }
  }

  private final Map<Integer, Integer> counter;
  private final PriorityQueue<Data> stack;
  private int latest = 0;

  public FreqStack() {
    this.stack = new PriorityQueue<>((data, t1) -> {
      if (data.nowCount != t1.nowCount)
        return t1.nowCount - data.nowCount;
      else
        return t1.latest - data.latest;     
    });
    this.counter = new HashMap<>();
  }

  public void push(int val) {
    counter.put(val, counter.getOrDefault(val, 0) + 1);
    stack.add(new Data(val, counter.get(val), latest++));
  }

  public int pop() {
    final Data poll = stack.poll();
    counter.put(poll.number, counter.getOrDefault(poll.number, 1) - 1);
    return poll.number;
  }
}

설명

스택의 pop을 할때에는 stack 내 가장 많이 들어있는 값을 꺼내야 한다.

만약 가장 많은 갯수가 여러개인 경우, 가장 최근에 Push된 숫자를 꺼내야 한다.

ex) 5, 4, 5, 4, 7 push 후 pop을 하면 -> 4가 꺼내져야 함

 

그래서 2가지 key로 내림차순 정렬하는 Priority Queue 를 만든다. (Max Heap)

첫번째 key는 push될 당시의 해당 숫자의 갯수

두번째 key는 push될 당시의 stack 높이 값이다. 

 

두번째 key의 존재 덕분에, 가장 최근에 push된 숫자를 제일 먼저 poll 할 수 있다.

만약 이 key가 없다면 아래 순으로 push 후 pop을 하면 답과 다른 결과가 나온다.

int[] g = {5,1,2,5,5,5,1,6,1,5};

 

알게 된 것

1. 리트코드는 debug와 run test 의 결과가 다르게 나오는 버그(?) 가 있다. 이 경우에는 Comparable<Data> interface를 구현하려고 하니 결과가 다르게 나왔다. 그래서 람다함수로 Comparator 함수를 만들어 비교하게 하였다.

 

2. compareTo() 함수를 구현할 때, 2가지 이상의 key로 대소를 구분하려면 위처럼 하면 된다.

 

3. PQ의 내림차순정렬을 하고 싶다면, 비교하는 object의 값에 대상 object 값을 빼면 된다.

4. 실행할때마다 run time 이 다르게 나온다. 이건 너무 신경안써도 될듯 싶다.