[코테연습] 1975. Maximum Matrix Sum

문제타입

• Greedy Algorithm
• Matrix Manipulation
• Mathematics

문제분석

• 주어진 행렬에서 각 행과 열을 적어도 한 번은 뒤집을 수 있는 조건에서, 행렬의 모든 값을 더한 합을 최대로 만드는 것이 목표.
• 중요한 관찰:
  1. 행 또는 열을 뒤집으면 그 열 또는 행의 값들이 부호가 바뀐다.
  2. 뒤집는 횟수는 제한이 없으므로 부호 전환은 자유롭게 이루어질 수 있다.
  3. 행렬 내 음수의 개수와 최소 절대값 요소가 결과에 영향을 준다.
• 핵심 전략:
  • 음수의 개수가 짝수이면 모든 음수를 양수로 바꿀 수 있다.
  • 음수의 개수가 홀수이면 최소 절대값을 갖는 요소 하나를 양수로 만들지 못해 음수로 남긴다.

문제풀이

1. 행렬 절대값의 합 계산:
   • 행렬의 모든 값을 양수로 간주하고 합을 계산한다.
2. 음수 개수 파악:
   • 행렬 내 음수의 개수를 세어 짝수인지 홀수인지 판단한다.
3. 최소 절대값 찾기:
   • 음수로 남길 수밖에 없는 값이 발생할 경우 최소한의 손실을 주기 위해 최소 절대값을 찾는다.
4. 최종 결과 계산:
   • 음수의 개수가 짝수라면 절대값의 합이 그대로 결과가 된다.
   • 음수의 개수가 홀수라면 절대값의 합에서 최소 절대값의 두 배를 뺀 결과가 된다.

 

> java

 

class Solution {
    public long maxMatrixSum(int[][] matrix) {
    int min = Integer.MAX_VALUE;
    long sum = 0;
    int negCount = 0; 
    for(int i=0; i<matrix.length; i++)
    for(int j=0; j<matrix[0].length; j++)
    {
     if(matrix[i][j]<0)
     negCount++;
     int ab = Math.abs(matrix[i][j]);
     min = Math.min(min, ab);
     sum += ab;    
    }
    if(negCount%2==0)
    return sum; 
    return sum - 2*min;
}
}

 

> python

 

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total_sum = 0
        negative_count = 0
        min_abs_value = float('inf')
        
        for row in matrix:
            for value in row:
                total_sum += abs(value)
                if value < 0:
                    negative_count += 1
                min_abs_value = min(min_abs_value, abs(value))
        
        # If the count of negative numbers is odd, subtract twice the smallest absolute value
        if negative_count % 2 == 1:
            total_sum -= 2 * min_abs_value
        
        return total_sum