[알고리즘] 2차원 배열 90도 회전하기
코딩 테스트 구현 문제에서는 2차원 배열을 90도, 180도, 270도 회전해야 하는 경우가 종종 등장한다.
이번 포스팅에서는 2차원 배열을 시계 방향으로 90도 회전하는 공식 과 구현 방법을 정리한다.
2차원 배열 90도 회전
N × N 크기의 2차원 배열이 있다고 가정하자.
1 2 3
4 5 6
7 8 9
이를 시계 방향으로 90도 회전하면 다음과 같다.
7 4 1
8 5 2
9 6 3
이때 사용할 수 있는 공식은 다음과 같다.
v90[i][j] = v[N - j - 1][i]
v: 원본 배열v90: 90도 회전한 배열N: 배열의 크기i,j: 회전한 배열의 행과 열 인덱스
왜 이 공식으로 회전할 수 있을까?
시계 방향으로 90도 회전하면 원본 배열의 좌표 (r, c)는 (c, N - 1 - r)로 이동한다.
즉 원본의 열 인덱스가 새로운 행 인덱스가 되고, 원본의 행 인덱스는 역순으로 새로운 열 인덱스가 된다.
이를 반대로 생각하면 회전한 배열의 (i, j)에 들어갈 값은 원본 배열의 (N - j - 1, i)에 위치한다.
따라서 다음 공식이 성립한다.
v90[i][j] = v[N - j - 1][i]
예를 들어 N = 3일 때,
v90[0][0] = v[2][0]; // 7
v90[0][1] = v[1][0]; // 4
v90[0][2] = v[0][0]; // 1
첫 번째 행이 7 4 1로 구성되면서 시계 방향으로 회전하는 것을 확인할 수 있다.
C++ 구현
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N = 3;
vector<vector<int>> v = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
vector<vector<int>> v90(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
v90[i][j] = v[N - j - 1][i];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << v90[i][j] << " ";
}
cout << "\n";
}
return 0;
}
🔽 출력 :
7 4 1
8 5 2
9 6 3
시간 복잡도
N × N 크기의 배열을 이중 반복문으로 순회하며 모든 원소를 한 번씩 이동한다.
따라서 시간 복잡도는 O(N²) 이다.
새로운 N × N 배열을 생성하므로 공간 복잡도 역시 O(N²) 이다.
마무리
2차원 배열의 시계 방향 90도 회전은 다음 공식만 기억하자.
v90[i][j] = v[N - j - 1][i]
Leave a comment