99클럽 코테 스터디 36일차 TIL + 우선순위 큐 (Priority Queue), 이진 힙 (Binary Heap), [leetcode] Delete Greatest Value in Each Row

✨ 문제 

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.

 

https://leetcode.com/problems/delete-greatest-value-in-each-row/description/

 

 

 

✨ 개념

우선순위 큐 (Priority Queue)

- 우선순위 큐는 각 요소에 우선순위를 지정할 수 있다.

- 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리된다.

- 우선순위 큐는 보통 배열이나 연결 리스트 등으로 구현될 수 있지만, 가장 효율적인 구현은 이진 힙(Binary Heap)이다.

 

이진 힙 (Binary Heap)

- 이진 힙은 부모 노드가 자식 노드보다 우선순위가 높거나 같은 완전 이진 트리 구조를 갖는다.

 

 

 

✨ 최종코드

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int result = 0; // 최종 결과를 저장할 변수
        
        // 각 행을 정렬
        for (int[] row : grid) {
            Arrays.sort(row);
        }
        
        int m = grid.length; // 행의 수
        int n = grid[0].length; // 열의 수

        // 모든 열에 대해 반복
        for (int col = n - 1; col >= 0; col--) {
            int maxDeleted = Integer.MIN_VALUE; // 각 반복에서 삭제된 값 중 최대 값을 저장할 변수
            // 각 행에 대해 반복
            for (int row = 0; row < m; row++) {
                // 현재 열의 값을 가져옴
                int value = grid[row][col];
                // 삭제된 값 중 최대 값을 업데이트
                maxDeleted = Math.max(maxDeleted, value);
            }
            // 최대 값을 결과에 더함
            result += maxDeleted;
        }

        return result; // 최종 결과 반환
    }
}