본문으로 바로가기
반응형

Description

주어진 2N2N 크기의 배열에서 각 요소의 위치를 바꿔 nn의 크기의 요소의 합이 가장 큰 값을 반환하는 문제입니다.

Solution 1. Matrix

public static int flippingMatrix(List<List<Integer>> matrix) {
    // Write your code here
    int m = matrix.size();
    int n = matrix.get(0).size();
    int sum = 0;

    //Divide size by 2 to get quadrant size
    int quadSize = matrix.size()/2;
    //Now for each cell in the upper quadrant, get the max value that could be flipped into that cell

    //Iterate all rows in quadrant
    for(int r = 0; r < quadSize; r++)
    {
        //Iterate all columns in quadrant
        for(int c = 0; c < quadSize; c++)
        {
            //Grab the 4 possible values that could wind up in this location of the upper quadrant
            int p1 = matrix.get(r).get((2*quadSize) - c - 1);
            int p2 = matrix.get(r).get(c);
            int p3 = matrix.get((2*quadSize) - r - 1).get(c);
            int p4 = matrix.get((2*quadSize) - r - 1).get((2*quadSize) - c - 1);

            //Get the highest value possible in this cell
            sum += Math.max(p1, Math.max(p2, Math.max(p3, p4)));
        }
    }

    return sum;
}
  1. 매트릭스 가장 좌측상단의 1열1행에 있는 값은 아무리 회전한들 결국 존재할 수 있는 위치는 n열n행, 1열 n행, n열 1행, 1열1행 4곳밖에 존재 할 수 없다
  2. 반대로 그 4곳에 위치하는 값중 가장 큰 값이 1열1행에 존재하게 됩니다.
  3. 모든 나머지 매트릭스의 위치값들도 matrix[i][j], matrix[i][n-j-1], matrix[n-i-1][j], matrix[n-i-1][n-j-1] 이 4개의 값 중 가장 큰 값이 좌측상단에 오게되고 그 값의 합을 구하면 된다

Reference

 

Flipping the Matrix | HackerRank

Reverse rows and columns of a matrix to maximize the sum of the elements in the upper-left quadrant.

www.hackerrank.com

반응형

댓글을 달아 주세요