99클럽(2기) - 코테스터디 27일차 TIL # Max Heap # Priority Queue

LeetCode - 2500. Delete Greatest Value in Each Row

You are given an m x n matrix grid consisting of positive integers.

Perform the following operation until grid becomes empty:

• Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
• Add the maximum of deleted elements to the answer.

 

Note that the number of columns decreases by one after each operation.

Return the answer after performing the operations described above.

---

 

1. 풀이

1) 각 행마다 max heap 생성

 모든 열이 없어질 때까지 항상 행의 최대값을 삭제해야 하므로 우선순위 큐로 max heap을 구현한다. max heap은 '항상 루트를 최대값을 가진 노드로 유지'하려는 속성을 가지고 있기 때문이다. poll()은 루트를 삭제하는 동시에 해당 값을 반환해주며, max heap은 최대값을 가진 노드를 루트로 교환한다. min heap의 경우에는 이 반대이다.

 

2) grid가 빌 때까지 아래 로직 반복

  2-1) finalMaxValue를 int의 최소값으로 초기화한다. finalMaxValue의 초기값은 무조건 첫 번째 currentMaxValue보다 작아야 하므로 Integer의 최소값 -2147483648으로 설정해준다. 

 

  2-2) maxHeap의 행을 순회하며 poll()을 통해 반환받은 최대값을 currentMaxValue에 할당한다. 각 행의 최대값 currentValue와 지금까지의 최대값 finalMaxValue끼리 비교해서 더 큰 값을 finalMaxValue로 갱신한다. 모든 행의 갱신이 끝나면 모든 행은 하나의 열이 사라진 상태이며, 그 중 가장 큰 값을 가진 열의 값이 finalMaxValue가 된다.   

 

  2-3) 각 행의 최대값 중 가장 큰 값을 totalSum에 더해준 후 열의 수를 1 감소시킨다. 

 

3) totalSum 반환

 모든 열이 없어졌을 때는 totalSum에 매 삭제 시의 각 행에서의 최대값이 모두 더해진다. 마지막으로 totalSum을 반환해준다. 

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int m = grid.length; // grid의 행 길이
        int n = grid[0].length; // grid의 열 길이
        int totalSum = 0;

        // 각 행마다 max heap 생성
        PriorityQueue<Integer>[] maxHeap = new PriorityQueue[m];
        for (int i = 0; i < m; i++) {
            maxHeap[i] = new PriorityQueue<>(Collections.reverseOrder());
            for (int j = 0; j < n; j++) {
                maxHeap[i].add(grid[i][j]); // max heap에 값 입력 
            }
        }

        // grid가 빌 때까지 아래 로직 반복
        while (n > 0) {
            int finalMaxValue = Integer.MIN_VALUE;

            // 행마다 최대값 삭제 후 최대값 비교
            for (int i = 0; i < m; i++) {
                if (!maxHeap[i].isEmpty()) {
                    int currentMaxValue = maxHeap[i].poll();
                    finalMaxValue = Math.max(finalMaxValue, currentMaxValue);
                }
            }

            // 각 행의 최대값 중 가장 큰 값을 totalSum에 더해줌
            totalSum += finalMaxValue;

            // 열의 수를 1 감소시킴
            n--;
        }

        return totalSum;
    }
}

 

 

2. 새롭게 알게 된 점

•  java에서 우선순위 큐(PriorityQueue)의 기본 설정은 min heap이다! 즉, 루트를 최소값으로 유지하는 완전 이진 트리(complete binary tree)다. 따라서 max heap을 사용하려면 PriorityQueue 생성자 파라미터에 Collections.reverseOrder()를 전달해야 한다. 
• 원시타입의 래퍼클래스들인 Integer, Byte, Long, Short는 MAX_VALUE, MIN_VALUE를 제공해서 하드코딩하지 않고 안전하게 각 타입의 최대, 최소값을 사용할 수 있다. 예를 들어 Integer.MAX_VALUE를 할당한 정수형 변수 2147483647의 값을, Integer.MIN_VALUE를 할당한 정수형 변수는 -2147483648의 값을 갖게 된다.
• Priority Queue의 메소드들
  • add(1): 해당 값을 가진 노드 추가(추가가 불가능한 경우 예외 발생)
  • offer(1): 해당 값을 가진 노드 추가(추가가 불가능한 경우 false 반환)
  • poll(): 루트 삭제 및 해당 값 반환
  • peek(): 루트 값 반환
  • remove(): 루트 삭제
  • clear(): 모든 노드 삭제
  • size(): 모든 노드의 수 반환
  • isEmpty(): 우선순위 큐가 비어있으면 true 반환