N×N 크기의 정사각 행렬이 주어졌을 때, 이 행렬을 시계 반대 방향(반시계 방향)으로 90도 회전하는 것이 과제입니다. 예를 들어 다음과 같습니다.
입력 −
N = 3
matrix[ ][ ] = [
[1 2 3],
[4 5 6],
[7 8 9]
]출력 −
3 6 9 2 5 8 1 4 7
설명: 행렬을 시계 반대 방향으로 90도 회전하면 위와 같이 3 6 9 2 5 8 1 4 7 순서의 결과가 생성됩니다.
문제 해결 접근 방식
핵심 아이디어는 먼저 주어진 행렬의 전치 행렬(transpose)을 구한 뒤, 각 열(column)의 요소들을 위아래로 뒤집는 것입니다. 즉, 첫 번째 행의 요소와 마지막 행의 요소를 서로 교환하면 반시계 방향 회전이 완성됩니다.
- 정사각 행렬을 입력받습니다.
- 행렬의 전치 행렬(transpose)을 구합니다. 즉, 행과 열을 서로 맞바꿉니다.
- 각 열에서 인덱스 0의 요소와 인덱스 n-1의 요소를 서로 교환합니다.
- 최종 결과를 반환합니다.
예제 코드
import java.io.*;
class Solution {
static void rotateMatrix(
int n, int matrix[][]){
// 1단계: 전치 행렬 구하기
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 2단계: 각 열의 요소를 위아래로 뒤집기
for(int i=0;i<n;i++){
int top = 0;
int bottom = n-1;
while(top<bottom){
int temp = matrix[top][i];
matrix[top][i] = matrix[bottom][i];
matrix[bottom][i] = temp;
top++;
bottom--;
}
}
}
static void displayMatrix(int N, int mat[][]){
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + mat[i][j]);
System.out.print("\n");
}
System.out.print("\n");
}
public static void main(String[] args){
int N = 3;
int mat[][] = {
{1,2,3},
{4,5,6},
{7,8,9}
};
rotateMatrix(N, mat);
displayMatrix(N, mat);
}
}실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
3 6 9 2 5 8 1 4 7
동작 원리 정리
이 알고리즘은 두 단계로 나눌 수 있습니다. 첫 번째 단계에서는 matrix[i][j]와 matrix[j][i]를 교환하여 전치 행렬을 만듭니다. 두 번째 단계에서는 각 열을 기준으로 위쪽(top)과 아래쪽(bottom) 포인터를 사용해 요소를 맞바꿈으로써 반시계 방향 90도 회전 효과를 얻습니다. 전체 연산은 O(N²)의 시간 복잡도를 가지며, 추가 배열 없이 제자리(in-place)에서 처리되므로 공간 복잡도는 O(1)입니다.