[99클럽 23일차] [LeetCode] 2500. Delete Greatest Value in Each Row

문제 설명

이 문제는 m x n 크기의 2차원 배열에서 아래의 과정을 반복하여 최종 결과를 구해야 한다.

1. 각 행에서 가장 큰 값을 삭제 (같은 값을 가진 요소가 여러 개 있으면 임의로 하나 삭제 가능)
2. 삭제된 값들 중 가장 큰 값을 결과에 더함.
3. 모든 열이 삭제될 때까지 위 과정을 반복

문제 해결 전략

문제 분석

1. 각 행을 오름차순 정렬한다. 각 작업 후에는 마지막 열의 값(=최댓값)을 가져오면 된다.

2. 열 단위로 반복하며 삭제된 값 중 가장 큰 값을 찾는다.

3. 배열 크기가 최대 50 x 50이기 때문에 행 정렬과 열 최대값 계산을 반복해도 시간 복잡도가 허용 범위 내라고 예상한다.

구현 코드

import java.util.*;

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int result = 0;

        // 각 행을 정렬 (오름차순)
        for (int i = 0; i < m; i++) {
            Arrays.sort(grid[i]);
        }

        // 열 별로 최대값을 선택하고 결과에 더함
        for (int j = n - 1; j >= 0; j--) { // 열 개수만큼 반복
            int maxInColumn = 0;
            for (int i = 0; i < m; i++) {
                maxInColumn = Math.max(maxInColumn, grid[i][j]); // 현재 열의 최대값 찾기
            }
            result += maxInColumn; // 최대값 누적
        }

        return result;
    }
}