[leetcode-48] Rotate Image

LeetCode-48

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

note : 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.

Answer

        :::python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        if len(matrix[0])==1:
            return None
        max_length = len(matrix[0])
        matrix = collections.deque(matrix)
        for i in range(max_length):
            for j in range(max_length):
                matrix[j].append(matrix[max_length-i-1].pop(0))

Result : 43ms Memory: 16.3mb

문제

주어진 2D 배열을 90도 회전시키는 문제입니다.

예시

예시 입력 배열:

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

예시 출력 배열:

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

접근 방법

이 문제를 풀기 위해서는 이차원 배열에서 행과 열의 위치를 바꾸는 것이 필요합니다. 이를 처리하기 위해서는 다음과 같은 두 가지 방법이 있습니다.

행과 열 바꾸기

우선 행과 열의 위치를 바꿔보겠습니다. 예시 배열을 바꾸면 다음과 같은 모양을 가지게 됩니다.

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

이제 각 행을 뒤집으면 회전된 배열이 완성됩니다.

대각선 기준 바꾸기

대각선에 대해 대칭을 만들어 보겠습니다.
예시 배열을 대각선으로 뒤집으면 다음과 같은 모양을 가지게 됩니다.

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

이제 각 형태는 둘 다 같은 모양입니다. 이 중에서 각 행을 뒤집어주면 회전된 배열이 완성됩니다.

시간 복잡도

이 문제의 시간 복잡도는 O(n^2)입니다. 이는 주어진 배열의 모든 요소를 한 번씩만 방문해서 처리하게 되기 때문입니다.