[LeetCode] 48. Rotate Image

문제

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

48. Rotate Image는 n x n 2차원 행렬을 오른쪽으로 90도 회전하는 문제다. 이때 추가 공간을 사용하지 않고 주어진 행렬을 제자리에서 변환해야 한다.

BCR(Best Conceivable Runtime)

2차원 행렬의 모든 원소를 각 한 번씩은 탐색할 필요가 있기 때문에 $O(N^2)$이다.

풀이 1

첫 번째 방법은 행렬의 가장 밖의 껍데기에서 안으로 들어가면서 90도씩 회전시키는 방법이다.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n/2; layer++) {
            int start = layer;
            int end = n - 1 - layer;
            for (int i = start; i < end; i++) {
                int temp = matrix[i][start];
                int offset = start + end - i;
                matrix[i][start] = matrix[end][i];
                matrix[end][i] = matrix[offset][end];
                matrix[offset][end] = matrix[start][offset];
                matrix[start][offset] = temp;
            }
        }
    }
}

90도 회전시킬때 서로 대응하는 원소들의 위치를 계산한다고 애먹었다..

풀이 2

두 번째 방법은 Discussion에서 본 방법인데, 아주 짧고 간단하게 해결할 수 있다. 전치 행렬로 만든 뒤 각 행을 뒤집는 방법이다. 배열을 회전시키는 문제는 여러 문제에서 응용되기 때문에 외우고 있을 수록 편리한데, 이 방법은 외우기도 쉽다.

코드는 다음과 같다.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                swap(matrix, i, j, j, i);
            }
        }
        for (int i = 0; i < n; i++) {
            reverseRow(matrix, i, 0, n-1);
        }
    }

    public void swap(int[][] matrix, int r1, int c1, int r2, int c2) {
        int temp = matrix[r1][c1];
        matrix[r1][c1] = matrix[r2][c2];
        matrix[r2][c2] = temp;
    }

    public void reverseRow(int[][] matrix, int r, int c1, int c2) {
        for (int i = 0; i <= (c1+c2)/2; i++) {
            swap(matrix, r, c1+i, r, c2-i);
        }
    }
}

만약 오른쪽으로 90도가 아닌 왼쪽으로 90도 돌리고 싶다면 전치 행렬로 만든 뒤 각 열을 뒤집으면 된다.

    public void reverseColumn(int[][] matrix, int c, int r1, int r2) {
        for (int i = 0; i <= (r1+r2)/2; i++) {
            swap(matrix, r1+i, c, r2-i, c);
        }
    }

풀이 1과 풀이 2 모두 시간 복잡도는 $O(N^2)$로 동일하다. 단 풀이 2는 전치 행렬과 역 연산으로 인해 풀이 1보다 각 원소의 방문 횟수가 더 많다는 것을 고려했을때, 풀이 2의 시간 복잡도는 풀이 1보다 상수항이 더 클 것이다.