[Leetcode] 48. Rotate Image

문제 바로가기

행렬을 시계방향 90도 회전시키는 문제.
회전을 할때 어떤 원소의 행과 열은 다음과 같이 바뀐다

row' = col
col' = (n - 1) - row

따라서 행렬을 순회하며 회전 결과 위치로 값을 옮겨주면 된다.
이 때 다음과 같은 최적화를 통해 계산 수를 줄일 수 있다.

1. 행 인덱스가 n-1인 모든 원소는 0인 원소들의 회전과정에서 이미 계산된다.
   => 0 <= r < n - 1 and 0 <= c < n - 1
2. 각 행의 회전을 계산하는 과정에서 양파 껍질을 벗기듯 바깥에서부터 한칸씩의 원소들이 계산되므로 열은 그만큼 계산을 줄일 수 있다.
   => r <= c < n - 1 - r
3. 2번에서 얻은 범위는 r < n // 2일 때만 성립한다. 또한 n이 홀수일 때 정가운데의 원소는 회전해도 제자리이다.
   => r < n // 2

Time Complexity: O(n^2)
Space Complexity: O(1)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for r in range(n // 2):
            for c in range(r, n - r - 1):
                nR, nC = c, n - 1 - r
                tmp = matrix[r][c]
                for i in range(4):
                    tmp, matrix[nR][nC] = matrix[nR][nC], tmp
                    nR, nC = nC, n - 1 - nR