Posted Updated

코딩 테스트 구현 문제에서는 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