[Leetcode] 48. Rotate Image (Python)

48. Rotate Image (Python)

 

Source

https://leetcode.com/problems/rotate-image/

Rotate Image - LeetCode

 

Code

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

    def temp(self, i, j, matrix):
        n = len(matrix)
        first = matrix[i][j]
        matrix[i][j] = matrix[n - 1 - j][i]
        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
        matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
        matrix[j][n - 1 - i] = first

 

How to solve?

90도 회전하면 

matrix[ i ][ j ]

-> matrix[ n - 1 - j ][ i ]

-> matrix[ n - 1 - i ][ n - 1 - j ]

-> matrix[ j ][ n - 1 - i ]

-> matrix[ i ][ j ]

위와 같은 순서로 회전한다.

재귀 등을 이용해 풀 수 있을 것 같은데 방법이 잘생각나지 않아 하드코딩으로 했다.

 

Reviewing the best code

https://leetcode.com/problems/rotate-image/solutions/842087/easy-python-from-scratch-2-steps/?orderBy=hot&languageTags=python3 

Easy Python from scratch (2 Steps) - Rotate Image - LeetCode

 

# reverse
l = 0
r = len(matrix) -1
while l < r:
	matrix[l], matrix[r] = matrix[r], matrix[l]
	l += 1
	r -= 1
# transpose 
for i in range(len(matrix)):
	for j in range(i):
		matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

 

1. reverse에서 row의 자리가 반대로 변하고

2. transpose에서 대각선을 기준으로 row와 column이 서로 교환된다.