HackerRank/Flipping the Matrix

Day 2 Interview Questions Mock Test .

행렬의 행과 열을 이리저리 회전시키고 1/4로 쪼갰을 때의 좌상단의 위치한 녀석의 최대 합을 구하는 문제.

처음에는 못 풀었다. 두번째 시도에 풀었다.

4x4 행렬을 생각했을 때, 0번째 '열'을 뒤집고 나면 3,0에 위치한 녀석은 다시 못 쓸것이라 생각했다. 근데 그게 아니고 3번째 행을 뒤집고 4번째 열을 뒤집고 다시 2번째 행을 뒤집으면 원래 1,0에 위치한 녀석을 다시 원래 위치로 돌릴 수 있다.

큐브를 좀 했던 사람이라면 쉽게 풀었을거 같지만 나는 큐브를 진짜 싫어했었어서 저 직관을 얻기까지 꽤 고전했다. 즉, 어떤 위치 [i,j]에 위치한 원소의 최대값은 다른 녀석들에 종속적이지 않다. 독립적으로 구할 수 있다는 직관을 믿고 다음과 같이 식을 썼다.

int size = matrix.size();
int element = max(matrix[i][j], matrix[i][size-j-1], matrix[size-i-1][j], matrix[size-i-1][size-j-1]);

i,j가 가질 수 있는 최대값은
1. (i,j)
2. 행을 뒤집었을 때 오는 (i, size-j-1) 값
3. 열을 뒤집었을 때 오는 (size-i-1, j) 값
4. 행과열 모두 뒤집었을 때 오는 (size-i-1, size-j-1) 값
4가지가 있다. 아까 독립적이라는 직관을 믿기로 했으므로, 이 식을 그대로 쓰면 다음과 같이 문제에서 요구하는 함수를 완성할 수 있다.

int flippingMatrix(vector<vector<int>> matrix) {
    int size = matrix.size();
    int sum = 0;
    for (int i = 0; i < matrix.size() / 2; ++i)
    {
        for (int j = 0; j < matrix.size() / 2; ++j) {
            int max = matrix[i][j] > matrix[i][size - j - 1] ? matrix[i][j] : matrix[i][size - j - 1];
            max = max > matrix[size - i - 1][j] ? max : matrix[size - i - 1][j];
            max = max > matrix[size - i - 1][size - 1 - j] ? max : matrix[size - i - 1][size - 1 - j];
            sum += max;
        }
    }
    return sum;
}

문제없이 100점이 나왔으므로, 어느정도 직관을 믿을 수 있게 되었다.