[99클럽 4기 코테 스터디 TIL 23일차] 2500. Delete Greatest Value in Each Row (feat. 최대힙, 그리드를 최대힙 리스트로 변환)

1) 문제

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

 

 

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.

 

Example 1:

Input: grid = [[1,2,4],[3,3,1]]
Output: 8
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
The final answer = 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[10]]
Output: 10
Explanation: The diagram above shows the removed values in each step.
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
The final answer = 10.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 100

 

 

 

 

2) 내가 구현한 코드

import java.util.*;

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int answer = 0;
        int maxNum =0;
        int compareNum=0;
        PriorityQueue<Integer> pq;
        ArrayList<PriorityQueue> heapList = new ArrayList<>();

        //그리드를 최대 힙 리스트로 변환
        for(int i=0; i<grid.length; i++){//row
            pq = new PriorityQueue<>(Collections.reverseOrder());
            for(int j=0; j<grid[i].length; j++){//column add
                pq.add(grid[i][j]);
            }
            heapList.add(pq);
        }
        // System.out.println(heapList); //[[4, 1, 2], [3, 3, 1]]

        while(!heapList.get(0).isEmpty()){
            for(int i=0; i<heapList.size(); i++){
                compareNum = (int)heapList.get(i).poll();
                if(maxNum < compareNum)maxNum = compareNum;
            }
            answer += maxNum;
            // System.out.println(maxNum); //4
            maxNum = 0; //초기화
            // System.out.println(heapList); //[[2, 1], [3, 1]]
        }
        return answer;
    }
}

 

3) 추가 문제

미들러 - 소수찾기

https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

챌린저 - 치킨 배달

https://www.acmicpc.net/problem/15686