[HackerRank] Flipping the Matrix

Problem

---

Sean invented a game involving a  2n×2n matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times. The goal of the game is to maximize the sum of the elements in the n×n submatrix located in the upper-left quadrant of the matrix.

 

Given the initial configurations for q matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix's upper-left quadrant is maximal.

 

Example

matrix = [ [1, 2], [3, 4]]

1 2
3 4

 

It is 2x2 and we want to maximize the top left quadrant, a 1x1 matrix. Reverse row 1 :

1 2
4 3

 

And now reverse column 0:

4 2
1 3

 

The maximal sum is 4.

 

Function Description

Complete the flippingMatrix function in the editor below.

flippingMatrix has the following parameters:

- int matrix[2n][2n]: a 2-dimensional array of integers

 

Returns

- int: the maximum sum possible.

 

Input Format

The first line contains an integer q, the number of queries.

The next q sets of lines are in the following format:

• The first line of each query contains an integer, n.
• Each of the next 2n lines contains 2n space-separated integers matrix[i][j] in row i of the matrix.

Sample Input

STDIN Function
----- --------
1 q = 1
2 n = 2
112 42 83 119 matrix = [[112, 42, 83, 119], [56, 125, 56, 49], \
56 125 56 49 [15, 78, 101, 43], [62, 98, 114, 108]]
15 78 101 43
62 98 114 108

 

Sample Output

414

 

Explanation

Start out with the following 2n x 2n matrix:

---

Sean은 각 셀에 정수가 들어 있는 2n×2n 행렬을 포함한 게임을 발명했습니다. 그는 행렬의 행이나 열을 원하는 만큼 뒤집을 수 있습니다. 게임의 목표는 행렬의 좌상단 사분면에 위치한 n×n 부분 행렬의 합을 최대화하는 것입니다.

주어진 여러 개의 행렬 구성에 대해, Sean이 각 행렬의 행과 열을 최적의 방법으로 뒤집어 행렬의 좌상단 사분면의 최대 합을 구할 수 있도록 도와주세요.

 

즉, 행렬을 4등분하여 2사분면의 합이 가장 크도록 행과 열을 뒤집은 후, 가장 큰 2사분면의 합을 구하는 문제이다. 

 

 

 

Solution

---

내가 쓴 답은 이렇다 

행렬의 각 사분면에서 최대값을 추출하여 sum을 업데이트하고, 최종적으로 가능한 최대 합을 반환

이를 통해 Sean이 원하는 최대 합을 계산

class Result {
    /*
     * Complete the 'flippingMatrix' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY matrix as parameter.
     */
    public static int flippingMatrix(List<List<Integer>> matrix) {
        // Write your code here
        int sum = 0;
        int n = matrix.size();
        
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                sum += Math.max(matrix.get(i).get(j),
                        Math.max(matrix.get(i).get(n - 1 - j),
                                Math.max(matrix.get(n - 1 - i).get(j),
                                        matrix.get(n - 1 - i).get(n - 1 - j))));
            }
        }
        return sum;
    }
}

 

 

1. 변수 초기화:
   • sum 변수를 0으로 초기화하여 최대 합을 저장
   • n은 행렬의 크기를 나타내며, matrix.size()를 통해 2n2n2n 행렬의 한 변의 길이를 얻는다.
2. 중첩 루프:
   • 외부 루프는 행의 첫 번째 반을 반복
   • 내부 루프는 열의 첫 번째 반을 반복
   • 이를 통해 좌상단 사분면의 요소들을 검사
3. 최대 값 계산:
   • Math.max를 사용하여 네 개의 값 중 최대 값을 선택:
     • matrix.get(i).get(j): 좌상단
     • matrix.get(i).get(n - 1 - j): 우상단
     • matrix.get(n - 1 - i).get(j): 좌하단
     • matrix.get(n - 1 - i).get(n - 1 - j): 우하단
   • 각 반복에서 선택한 최대 값을 sum에 더한다.
4. 결과 반환:
   • 최종적으로 계산된 최대 합을 반환

 

 

❕ Math.max()

• 기능: 두 개의 숫자 중에서 더 큰 값을 반환
• 형식: Math.max(a, b)
  • a와 b는 비교할 두 숫자
• 사용 예:
   
• 코드에서의 사용:
  • 이 함수는 네 개의 값 중 최대 값을 선택하기 위해 중첩된 Math.max 호출로 사용
  • 예를 들어:

sum += Math.max(matrix.get(i).get(j),
         Math.max(matrix.get(i).get(n - 1 - j),
         Math.max(matrix.get(n - 1 - i).get(j),
         matrix.get(n - 1 - i).get(n - 1 - j))));

 

• 여기서, 각 호출은 해당 위치의 네 개의 값 중에서 최대 값을 선택하여 sum에 더한다.

---

https://medium.com/@subhanusroy/flipping-the-matrix-hackerrank-optimised-solution-in-c-java-python-with-explanation-a3dad70149ee

나도 이 사이트를 참고했다. 다른 언어로 풀이된 버전도 있으니 확인해보면 좋을 것 같다. 

Flipping the Matrix HackerRank Optimised Solution in C++, Java, Python with Explanation