파이썬(Python)으로 n×n 행렬을 시계 방향 90도 회전하기

문제 개요

n × n 크기의 2차원 행렬이 하나 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 이 행렬을 시계 방향으로 90도 회전하는 것입니다.

예를 들어 다음과 같은 행렬이 있다면,

회전 후의 출력 결과는 다음과 같습니다.

핵심 아이디어

행렬을 시계 방향으로 90도 회전하면 원본 행렬의 각 열을 아래에서 위로 읽은 값이 회전된 행렬의 한 행이 된다는 규칙이 있습니다. 즉, 첫 번째 열의 맨 아래 값이 새 행렬의 첫 번째 행 첫 번째 값이 되는 식입니다. 이 규칙만 이해하면 코드 작성이 훨씬 쉬워집니다.

해결 절차

• 회전 결과를 담을 임시 행렬 temp_mat = [] 를 준비하고, col := 행렬의 길이 - 1 로 설정합니다.
• 열 인덱스 col을 0부터 행렬의 길이까지 순서대로 반복합니다.
  • 매 반복마다 빈 리스트 temp := [] 를 생성합니다.
  • 행 인덱스 row를 행렬의 길이 - 1부터 0까지 역순으로 반복하면서 temp에 matrix[row][col] 값을 추가합니다.
  • 완성된 temp를 temp_mat에 추가합니다.
• 마지막으로 i와 j 두 인덱스를 사용해 temp_mat의 값을 원본 matrix에 그대로 복사하여 제자리(in-place) 회전을 완성합니다.

아래 구현 예제를 통해 더 자세히 살펴보겠습니다.

예제 코드 (Python)

class Solution(object):
    def rotate(self, matrix):
        temp_matrix = []
        column = len(matrix) - 1
        for column in range(len(matrix)):
            temp = []
            for row in range(len(matrix) - 1, -1, -1):
                temp.append(matrix[row][column])
            temp_matrix.append(temp)
        for i in range(len(matrix)):
            for j in range(len(matrix)):
                matrix[i][j] = temp_matrix[i][j]
        return matrix

ob1 = Solution()
print(ob1.rotate([[1,5,7],[9,6,3],[2,1,3]]))

입력

[[1,5,7],[9,6,3],[2,1,3]]

출력

[[2, 9, 1], [1, 6, 5], [3, 3, 7]]

복잡도 분석

시간 복잡도: O(n²) — 행렬의 모든 원소를 한 번씩 처리해야 하기 때문입니다.
공간 복잡도: O(n²) — 회전 결과를 잠시 저장할 임시 행렬(temp_matrix)이 필요합니다. 추가 메모리 없이 제자리 회전을 하려면 행렬을 먼저 전치(transpose)한 뒤 각 행을 좌우로 뒤집는 방법도 활용할 수 있습니다.