문제 설명#
Rotate Image - LeetCode
주어진 N × N 크기의 정사각형 행렬(matrix) 을 시계방향으로 90도 회전하는 문제입니다.
✅ 제약 조건
N × N (정사각형 행렬)- 추가 행렬 없이(in-place) 변환해야 함
1️⃣ 브루트포스 (새로운 행렬 사용)#
- 새로운 행렬
rotated를 만들어 회전 후 복사 - 추가 메모리 사용 → 비효율적 (O(N²) 공간)
- 문제에서 추가 공간 없이 해결해야 하므로 사용 불가능
2️⃣ 최적화된 O(N²) 풀이 (전치 행렬 + 반전) [추천]#
✔ 2단계 접근법으로 해결 가능
전치 행렬 (Transpose Matrix)
matrix[i][j] ↔ matrix[j][i] 로 교환- 행과 열을 바꿈
각 행을 뒤집기 (Reverse Rows)
코드 풀이#
Python#
1
2
3
4
5
6
7
8
9
10
11
| def rotate(matrix):
n = len(matrix)
# Step 1: 전치 행렬 만들기 (Transpose)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: 각 행을 뒤집기 (Reverse Rows)
for row in matrix:
row.reverse()
|
1
2
3
4
5
6
7
8
9
| def rotate(matrix):
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - i - 1):
temp = 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] = temp
|
Javascript#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var rotate = function(matrix) {
let n = matrix.length;
// Step 1: 전치 행렬 만들기 (Transpose)
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Step 2: 각 행을 뒤집기 (Reverse Rows)
for (let row of matrix) {
row.reverse();
}
};
|
참고 및 출처#
programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform