본문 바로가기

문제 풀기/코딩인터뷰

[코딩인터뷰 완전정복] 1.7 행렬 회전

Q : 이미지를 표현하는 N*N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가?

#include <iostream>

int** RotateMatrix(int* matrix[], int n) {
	int temp;
	for (int i = 0; i <= (n - 1) / 2; i++) {
		for (int j = 0; j <= (n - 1) / 2; j++) {
			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;
		}
	}
	return matrix;
}

void printMatrix(int * matrix[], int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d",matrix[i][j]);
		}
		printf("\n");
	}
}

int main() {
	int* input[10];
	for (int i = 0; i < 10; i++) {
		input[i] = new int[10]{1,2,3,4,5,6,7,8,9,0};
	}

	printMatrix(input, 10);
	RotateMatrix(input, 10);
	printMatrix(input, 10);

}

( i , j ) <= ( n-1-j , i ) 시계방향 90도 회전

추가 행렬이 없기 때문에 4개의 사분면중 하나의 분면에서만 작업하며 4개를 한번에 이동시킨다.

 

복잡도는 결과행렬을 만들어 하나씩 순서대로 변환시키는 것과 같다.