[leetCode/JS] 1975. Maximum Matrix Sum

난이도 [ 🤔 ] Medium

 

문제 설명 

You are given an n x n integer matrix. You can do the following operation any number of times: Choose any two adjacent elements of matrix and multiply each of them by -1. Two elements are considered adjacent if and only if they share a border. Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.

 

당신에게 n x n 크기의 정수 행렬이 주어집니다. 당신은 다음과 같은 연산을 원하는 만큼 수행할 수 있습니다.행렬에서 인접한 두 요소를 선택하고, 각각에 -1을 곱합니다.두 요소가 경계(변)를 공유하는 경우에만 인접한 것으로 간주합니다.당신의 목표는 행렬 내 모든 요소의 합을 최대화하는 것입니다. 위 연산을 사용하여 얻을 수 있는 행렬 요소 합의 최댓값을 반환하세요.

 

입출력 예

Example 1:

Input: matrix = [[1,-1],[-1,1]] 
Output: 4 
Explanation: We can follow the following steps to reach sum equals 4: 
 - Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.

 

 

Example 2:

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] 
Output: 16 
Explanation: We can follow the following step to reach sum equals 16: 
 - Multiply the 2 last elements in the second row by -1.

 

 

 

 

 

Constraints

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• -10^5 <= matrix[i][j] <= 10^5

 

 

 

---

내 솔루션

/**
 * https://leetcode.com/problems/maximum-matrix-sum
 * @param {number[][]} matrix
 * @return {number}
 *//**
 * @param {number[][]} matrix
 * @return {number}
 */

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var maxMatrixSum = function (matrix) {
    // 1차원 배열로 펼쳐서 처리 (가독성을 위해 flat 사용)
    const flatMatrix = matrix.flat();
    
    let numberOfMinus = 0; // 행렬 내 음수(-)의 총 개수
    let sum = 0;           // 모든 요소의 절댓값 합
    let minimunABS = Infinity; // 가장 작은 절댓값을 저장 (초기값은 무한대)

    for (let i = 0; i < flatMatrix.length; i++) {
        const val = flatMatrix[i];
        const absNum = Math.abs(val); // 현재 요소의 절댓값
        
        // 1. 모든 숫자를 양수로 가정하고 합산
        sum += absNum;
        
        // 2. 음수의 개수를 카운트
        // 인접한 두 수의 부호를 바꾸는 연산을 반복하면, 
        // 음수 부호를 원하는 위치로 이동시키거나 짝수개의 음수를 제거할 수 있음
        if (val < 0) numberOfMinus++;
        
        // 3. 행렬에서 절댓값이 가장 작은 숫자 찾기
        // 만약 음수가 홀수개라면, 전체 합에서 이 가장 작은 값을 음수로 남겨야 손해가 최소화됨
        if (minimunABS > absNum) minimunABS = absNum;
    }

    /**
     * 결과 반환 로직:
     * - 음수가 짝수개(numberOfMinus % 2 === 0): 
     * 모든 음수를 연산을 통해 양수로 바꿀 수 있으므로 전체 합(sum) 반환.
     * * - 음수가 홀수개: 
     * 무조건 한 개의 숫자는 음수로 남음. 가장 작은 숫자(minimunABS)를 음수로 선택.
     * 이미 sum에는 minimunABS가 양수로 더해져 있으므로, 
     * 이를 음수로 바꾸기 위해 sum에서 해당 값을 두 번 뺌 (sum - 2 * min).
     */
    return numberOfMinus % 2 === 0 ? sum : sum - (minimunABS * 2);
};

 

감상평

• 재미있는 문제. 구현이 어렵다기 보단 규칙을 찾아서 알고리즘을 만드는 이해력 문제
• const flatMatrix = matrix.flat(); 대신에 2중 for 문을 사용하면 100% 가능해짐.