[Leetcode 아주 상세한 문제풀이] 48. Rotate Image - 코드 line 별 설명

Leetcode 설명

이번에 풀어볼 문제는 리트코드 48번 문제 Rotate Image 다.

우선 문제를 살펴보자.

 

리트코드 48번 문제 Rotate Image 링크

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

Rotate Image - LeetCode

 

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.

 

 

문제 설명

문제를 간략히 살펴보자.

n by n 크기의 2D array가 주어지는데, 이 2D array를 시계 방향으로 90도 돌려 출력하라는 것이다.

위 예시 1번에서 보는 것처럼 5를 중심으로 시계방향으로 90도 돌리게 되면 오른쪽 예시와 같이 나온다.

n이 홀수일 경우 가장 안쪽에 위치한 숫자는 중심이기 때문에 움직이지 않지만, n이 짝수일 경우 위 예시 2번에서 보는 것처럼 아쪽에 위치한 sub 2D array [4, 8, 3, 6]가 시계 방향으로 90도 돌게된다.

이 문제의 제한조건 중 하나는 다른 2D array 만들어 그곳에 숫자들을 임시저장 할 수 없다는 것이다.

 

 

문제 접근법

이 문제를 푸는 방법은 고등교때 배웠던 행렬 연산식을 생각해보면 된다.

우선 주어진 2D 행렬 A가 아래와 같다고 생각해 보자.

A = | a11  a12  a13 ... a1n |
    | a21  a22  a23 ... a2n |
    (중략)| ...  ...  ... ... ... |
    | an1  an2  an3 ... ann |

그리고 위 행렬 A를 시계 방향으로 90도 돌렸을때 나오는 행렬을 B라고 생각해 보자.

B = | b11  b12  b13 ... b1n |
    | b21  b22  b23 ... b2n |
    (중략)| ...  ...  ... ... ... |
    | bn1  bn2  bn3 ... bnn |

 

그럼 위 행렬 A와 B의 관계는 아래와 같다.

b11 = an1

b12 = a(n-1)1

b13 = a(n-2)1

...

b1n = a11

 

즉, 우리가 구하고자 하는 행렬 B의 첫번째 행은 다음과 같다.

[b11, b12, b13, ..., b1n] = [an1, a(n-1)1, a(n-2)1, ..., a11]

위의 예시 1번의 경우를 살펴보면

[b11, b12, b13] = [a31, a21, a11] = [7, 4, 1]

이 되게되어 우리가 구하고자 하는 행렬이 된다.

위 행렬 연산에서 A와 B의 관계를 생각해보면 결국

a11, a12, a13 자리에 a31, a21, a11이 들어가야 하는 것이므로

A 행렬을 transpose 후 역순으로 배열하면 우리가 원하는 B 행렬을 구할수 있음을 알게된다.

 

 

문제 풀이

def rotate(matrix):
    n = len(matrix)
 
    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
 
    # Reverse each row
    for row in matrix:
        row.reverse()
 
# Test cases
matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate(matrix1)
print(matrix1)
 
matrix2 = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
rotate(matrix2)
print(matrix2)
 

 

 

관련 문제

리트코드 54번 Spiral matrix 문제 풀이 (링크)

리트코드 73번 Set matrix zeroes 문제 풀이 (링크)

리트코드 79번 Word search 문제 풀이 (링크)

 

 

48. Rotate Image