Leetcode 설명
이번에 풀어볼 문제는 리트코드 48번 문제 Rotate Image 다.
우선 문제를 살펴보자.
리트코드 48번 문제 Rotate Image 링크
https://leetcode.com/problems/rotate-image/
Rotate Image - LeetCode
Can you solve this real interview question? 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 [https://en.wikipedia.org/wiki/In-place_algorithm], which m
leetcode.com
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 행렬을 구할수 있음을 알게된다.
문제 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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)
|
cs |
관련 문제
리트코드 54번 Spiral matrix 문제 풀이 (링크)
리트코드 73번 Set matrix zeroes 문제 풀이 (링크)
리트코드 79번 Word search 문제 풀이 (링크)
'Leetcode > Matrix' 카테고리의 다른 글
[Leetcode 아주 상세한 문제풀이] 79. Word Search – 코드 line 별 설명 (1) | 2024.01.10 |
---|---|
[Leetcode 아주 상세한 문제풀이] 73. Set Matrix Zeroes - 코드 line 별 설명 (0) | 2024.01.09 |
[Leetcode 아주 상세한 문제풀이] 54. Spiral Matrix – 코드 line 별 설명 (1) | 2024.01.08 |