[leetCode/JS] 1975. Maximum Matrix Sum

문제 설명

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.

 

입출력 예

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] <= 105

---

내 솔루션

• 순간 어.. 인접한? 연결된? 이란 키워드를 보고 DFS같은걸 끼얹나? 싶었는데
• 직접 손으로 예제를 만들면서 테스트 해본 결과 규칙이 있는 것을 발견했다.
• 그 규칙대로 만약 -인 negative가 짝수개인 경우 모든 숫자의 절대값을 더하면 답이 된다.
• 만약 negative가 홀수 이면, 부호를 빼고 가장 작은 숫자의 2배 만큼 합산에서 빼주면 답이 된다.
• 그대로 코딩하여 실행했더니 통과!

var maxMatrixSum = function(matrix) {
  let min = Infinity;
  let sum = 0;
  let negative = 0;
  for(let i = 0; i < matrix.length ; i ++){
    for(let j = 0; j < matrix.length; j++) {
      sum += Math.abs(matrix[i][j]);
      min = Math.min(min, Math.abs(matrix[i][j]));
      if(matrix[i][j] < 0) negative++;
    }
  }
  if(negative % 2 === 1) sum -= (min * 2)
  return sum;
};

감상평

• 생각보다 짧고 간단한 코드지만 규칙을 찾기 전까지 살짝 오래걸렸다.
• 알고리즘 풀이는 정말 다크소울 같다. 하면 할 수록 이상한 놈들이 튀어나온다.