Day035 - 48. Rotate Image

48. Rotate Image

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.

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

내 풀이

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        matrix.T
        reverse_row
        """
        for i in range(len(matrix)):# 0, 1, 2
            r, c = 0, i
            while r < c:
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
                r += 1
                c -= 1

        for i in range(len(matrix)-1, 0, -1):# 0, 1, 2
            r, c = len(matrix)-1, i
            print(r, c)
            while r > c and c > 0:
                print(r, c)
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
                r -= 1
                c += 1

        # print("Transpose")
        # print(matrix)
        
        for r in range(len(matrix)):
            left, right = 0, len(matrix)-1
            while left < right:
                matrix[r][left], matrix[r][right] = matrix[r][right], matrix[r][left]
                left += 1
                right -= 1
        
        # print("reverse_row")
        # print(matrix)


        ## 모범 답안
        n = len(matrix)
    
        # 1. Transpose in place
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
       
        # 2. Reverse each row
        for i in range(n):
            matrix[i].reverse()

        ## numpy로 해결할 수 있긴 한데 matrix 자체를 수정할 수는 없는듯.
        import numpy as np
        matrix = np.array(matrix)
        matrix = matrix.T
        matrix = matrix[:, ::-1]


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix[0])
        for i in range(n // 2 + n % 2):
            for j in range(n // 2):
                tmp = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1]
                matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = matrix[i][j]
                matrix[i][j] = tmp

# Time Complexity : \(O(N)\)