[Java] LeetCode 2500. Delete Greatest Value in Each Row

[Java] LeetCode 2500. Delete Greatest Value in Each Row

 

문   제 : 

정수형 2차원 배열 grid가 주어진다.

직사각형으로 되어 있는 grid 배열의 각 행에서 최댓값을 가지는 요소를 삭제한다.

이렇게 모든 요소들이 삭제 될 때까지 삭제를 수행한다.

이 때 삭제된 요소들 중 가장 큰 값들을 모두 더한 값을 구하시오.

 

{ 1 <= 행, 열 <= 50 }

{ 1<= grid[i][j] <= 100 }

 

 

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 )

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.

 

---

접   근 : 

각 행에서 최댓값을 구한 뒤 삭제해주며 그 중 최댓값을 결과에 누적 합 해준다.

-> Brute Force 방식을 사용한다.

 

---

해   결 : 

grid 배열에 행, 열 순서로 접근한다.

 

각 행에서 최댓값을 구해준다.

각 행의 최댓값을 가진 부분은 다음 연산에는 빼야 하므로 0으로 값을 변경해준다. (삭제 효과)

 각 행의 최댓값중 최댓값을 구해 결과값에 저장해준다.

 

위 과정을 grid 배열의 열 개수 만큼 반복해준다.

 

따라서 3중 for문이 될 것

 

---

 

결과 값을 저장할 변수 res

열의 개수를 저장할 변수 col 선언

int res=0;
int col = grid[0].length;

 

 

---

 

삭제 횟수를 의미 하는 for문을 가장 위에 써준다.

결과값에 더해줄 최대값을 저장할 변수 rowMax를 초기화 해준다.

for(int k=0; k<col; k++){ // 삭제횟수
   int rowMax=0;
}

 

---

 

grid 배열에 행, 열 순서로 접근해 각 행의 최댓값(max)을 구한다.

최댓값을 구하면서 최댓값을 가지는 index도 같이 구해준 후(maxIndex)

최대값을 가졌던 부분의 값을 0으로 만들어준다. -> 삭제 효과

 

그리고 각 행의 최댓값중 최댓값을 구해준다. (rowMax)

 

for(int i=0; i<grid.length; i++){ // 행
    int max=0, maxIndex=0;
    for(int j=0; j<col; j++){ // 열
        if(max < grid[i][j]){
            max = grid[i][j];
            maxIndex = j;
        }
    }
	grid[i][maxIndex] = 0;
    rowMax = Math.max(rowMax, max);
}

 

---

 

결과값에 rowMax 를 누적합 해준다.

 

res += rowMax;

 

 

---

결   과  :

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int res=0;
        int col = grid[0].length;
       

        for(int k=0; k<col; k++){ // 삭제횟수
            int rowMax=0;
            for(int i=0; i<grid.length; i++){ // 행
                int max=0, maxIndex=0;
                for(int j=0; j<col; j++){ // 열
                    if(max < grid[i][j]){
                        max = grid[i][j];
                        maxIndex = j;
                    }
                }
                grid[i][maxIndex] = 0;
                rowMax = Math.max(rowMax, max);
            }
            res += rowMax;
        }


        return res;

    }
}