[해커랭크] (Constructive Algorithms) Flipping the Matrix

2nx2n 정수 행렬 게임
2nx2n 행렬이 주어졌을 때, 행 또는 열을 뒤집어 2사분면에 위치하는(nxn) 행렬의 합의 최댓값 구하기

조건

• 전달되는 행렬은 반드시 2nx2n의 2차원 배열, 각 인자는 정수

제한사항

• 1 ≤ q ≤ 16
• 1 ≤ n ≤ 128
• 0 ≤ matrix[i][j] ≤ 4096 (단, 0 ≤ i, j ≤ 2n)

 

나의 풀이

• 문제자체를 이해하지 못하여 다른 개발자들의 풀이를 찾아봄
  • 원본 링크: https://singo112ok.tistory.com/35
  • python 풀이이긴 하나, 작성한 내용을 보고 얼마나 간결하게 풀이했는지 알 수 있었음
  • 복잡한 로직을 간단하게 풀 수 있는 해법이 기발하여 기록하고자 함
• 타 개발자의 풀이내용을 내가 이해한 대로 설명 
  • 그림 1. 처럼 2nx2n 행렬에서 2사분면에 위치하는 nxn 행렬의 값이 최댓값이 되도록 각각의 행, 열 뒤집기
    • ex) 한 행의 배열을 뒤집거나, 한 열의 배열을 뒤집어 구하고자하는 위치에 최대한 큰 값이 오도록 하는 것

그림 1. 행렬 뒤집기 게임의 구조

• 그림 1. 의 우측에서 0,0에 위치할 수 있는 최댓값은  그림 2. 에서 표시된 네 귀퉁이의 값 중 하나
  • 즉, 원본링크에 풀이된 내용 처럼 최댓값은
    • (0,0) (0,2n) (2n,0) (2n,2n) 에 위치한 값 중 큰 값

그림 2. (0,0)에 위치할 최댓값 구하기

• 행과열을 각각 i, j 라고 할 때, 2사분면에 위치시킬 행렬의 최댓값은
  • (i, j) (i, n-j) (n-i, j) (n-i, n-j) 에 위치한 값 중 큰 값

// 생략

/*
 * Complete the 'flippingMatrix' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts 2D_INTEGER_ARRAY matrix as parameter.
 */

function flippingMatrix(matrix) {
  // Write your code here
  const n = matrix.length;
  let max = 0;
  for (let j = 0; j < n/2; ++) {
    for (let i = 0; i < n/2; i++) {
       max += Math.max(matrix[i][j], matrix[i][n-1-j], matrix[n-1-i][j], matrix[n-1-i][n-1-j]);
    }
  }
    
  return max;
}

// ..후략

결과