LeetCode 48. Rotate Image 문제 정의 및 풀이 코드 해설

1. 문제 정의

LeetCode 48번 Rotate Image 문제는 n x n 크기의 2차원 정수 행렬 matrix가 주어졌을 때, 이 행렬을 시계 방향으로 90도 회전시키는 문제이다.

단, 문제에서 요구하는 중요한 조건은 다음과 같다.

  • 입력 행렬은 정사각형 행렬이다.
  • 행렬을 시계 방향으로 90도 회전해야 한다.
  • 반환값은 없어야 한다.
  • matrix 자체를 수정해야 한다.
  • 즉, 함수 안에서 return으로 새 행렬을 반환하는 방식이 아니라, 기존 matrix가 회전된 결과를 가지도록 바꿔야 한다.

예를 들어 다음과 같은 행렬이 있다고 하자.

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

이 행렬을 시계 방향으로 90도 회전하면 다음과 같다.

matrix = [
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]

풀이 아이디어

기존 행렬의 첫 번째 행 [1, 2, 3]은 회전 후 오른쪽 열이 된다.

이 문제를 풀 때 집중한 점은 행렬의 원소가 기존 위치에서 회전 후 어느 위치로 이동하는지이다.

예를 들어 1 원소는 기존에 (0, 0) 위치에 있다가 회전 후 (0, 2) 위치로 이동한다.
2 원소는 (0, 1) 위치에 있다가 (1, 2) 위치로 이동한다.
3 원소는 (0, 2) 위치에 있다가 (2, 2) 위치로 이동한다.

즉, 기존에는 행이 0으로 고정되어 있던 줄이 회전 후에는 열 2를 고정으로 가지게 된다.

이를 이용하면 다음과 같은 코드로 행렬을 회전시킬 수 있다.

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        size = len(matrix)
        ResultMatrix = [[0] * size for i in range(size)]

        k = size - 1

        for i in range(size):
            for j in range(size):
                ResultMatrix[j][k] = matrix[i][j]
            k -= 1

        matrix[:] = ResultMatrix

이 코드는 기존 행렬의 각 행을 결과 행렬의 열로 옮기는 방식으로 작동한다.

처음에는 k = size - 1이므로 가장 오른쪽 열부터 채운다.
그 다음 한 행을 모두 처리할 때마다 k -= 1을 해주기 때문에, 오른쪽 열에서 왼쪽 열 방향으로 차례대로 값이 채워진다.

결국 기존 행렬의 첫 번째 행은 결과 행렬의 마지막 열이 되고, 두 번째 행은 그 왼쪽 열, 세 번째 행은 다시 그 왼쪽 열에 들어가게 된다.

마지막의 matrix[:] = ResultMatrix는 새로운 행렬을 반환하는 것이 아니라, 기존 matrix 리스트의 내용을 회전된 결과로 바꾸기 위해 사용한 것이다.