LeetCode - 48. Rotate Image

[LeetCode] 48. Rotate Image

LeetCode 48번 문제를 풀어보았다.. Link

Problem

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.

Intuition

이런 문제는 분명 예시안에 패턴이 있기 때문에 (사실 모든 문제가 그렇다) 그것을 찾는게 중요하다.

제한조건이 없다면 엄청나게 쉬운 문제지만 In-place 연산만을 해야한다는 점에서 까다로워졌다.

Approach

내가 예시 그림을 보면서 찾은 패턴은 시계방향으로 행렬을 회전하는 것은

1. 행렬을 Transpose하고
2. 행렬의 열의 순서를 거꾸로

하는 것이 같다는 것이다.

이를 그냥 In-place 연산하는 코드로 옮기기만 하면 된다.

Complexity

• Time complexity:

  시간복잡도는 행렬의 모든 cell의 개수를 M개라고 할 때, Transpose할 때 O(M), Reverse할 때 O(M)으로, 최종 O(M)이다.

• Space complexity: In-place 연산만 하기 때문에 O(1)이다.

My Code

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        len_m = len(matrix)
        for i in range(len_m):
            for j in range(i, len_m):
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp

        for i in range(int(len_m/2)):
            for j in range(len_m):
                temp = matrix[j][i]
                matrix[j][i] = matrix[j][len_m-1-i]
                matrix[j][len_m-1-i] = temp

        return matrix

이 방법말고도 꼬리의 꼬리를 물고 값을 하나씩 바꿔나가는 방법도 있다.

예를들어 3x3의 행렬이 있다고 할 때,

• (0,0) cell은 (0,2)로
• (0,2) cell은 (2,2)로
• (2,2) cell은 (2,0)로
• (2,0) cell은 (0,0)로

가고,

• (0,1) cell은 (1,2)로
• (1,2) cell은 (2,1)로
• (2,1) cell은 (1,0)로
• (1,0) cell은 (0,1)로

가는 것이 반복되기 때문에 이를 코드화하면 문제 해결이 가능하다.

코드는 더 짧아지고 영상으로 그 알고리즘이 어떻게 작동하는지 본다면 더 쉽다고 할 수도 있겠지만, 내 기준에 코드만 본다면 작동 방식을 이해하기 어려워보인다.