배열 돌리기(오른쪽, 왼쪽 돌리기)

 

문제 풀이 시, 배열을 돌리는 문제를 종종 만나게 된다.

돌리는 방법을 핵심적으로 정리하였다.

 

방법

오른쪽 돌리기 (90도)
- 1. 전치 행렬 수행
- 2. 수평 변환 수행

왼쪽 돌리기 (90도)
- 1. 전치 행렬 수행
- 2. 수직 변환 수행

 

N * N 배열을 90도 오른쪽으로 회전하는 알고리즘을 Java로 구현하려면 다음과 같은 절차를 따른다.

 

1. 전치: 배열의 행과 열을 바꾼다. 이 과정에서 배열의 (i, j) 위치에 있는 원소는 (j, i) 위치로 이동한다.

말이 어려워 보이지만, 사실 그냥 대각선을 기준으로 arr[i][j]를 arr[j][i]로 변경하라는 뜻이다.

		//1. 전치 수행
		for(int i = 0; i < N; i++) {
			for(int j = i; j < N; j++) {
				int temp = map[i][j];
				map[i][j] = map[j][i];
				map[j][i] = temp;
			}
		}

 

2. 수평 반전: 각 행의 원소 순서를 반대로 바꾼다. 이는 90도 오른쪽 회전과 같은 효과를 낸다.

이는 전치 행렬을 수행한 뒤, 각 행(i)을 수평으로 뒤집으라는 의미이다.

이를 위해 limit를 N의 절반만큼만 잡고, 이를 뒤집어주면 된다.

 

		//2. 수평 변환 수행(오른쪽으로 돌리기)
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N / 2; j++) { //절반만 변경하므로
				int temp = map[i][j];
				map[i][j] = map[i][N - j - 1];
				map[i][N - j - 1] = temp;
			}
		}

3.  수직 반전: 각 열의 원소 순서를 반대로 바꾼다. 이는 90도 오른쪽 회전과 같은 효과를 낸다.

오른쪽 회전과 반대로, 왼쪽 회전을 하기 위해서는 전치 행렬 수행 후 열 변환을 수행하여야 한다.

이는 행을 변경한다는 점만 제외하면 2와 로직상 동일하다.

 

 

		//3. 수직 변환 수행(왼쪽으로 돌리기)
		for(int j = 0; j < N; j++) {
			for(int i = 0; i < N / 2; i++) {
				int temp = map[i][j];
				map[i][j] = map[N - 1 - i][j];
				map[N - 1 - i][j] = temp;
			}
		}

코드

public class rotate {
	public static void main(String[] args) {
		int N = 4;
		int num = 1;
		int[][] map = new int[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = num++;
			}
		}
		
		//변경 전
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j]+"\t");
			}
			System.out.println();
		}
		System.out.println("================");
		//=======
		
		//1. 전치 수행
		for(int i = 0; i < N; i++) {
			for(int j = i; j < N; j++) {
				int temp = map[i][j];
				map[i][j] = map[j][i];
				map[j][i] = temp;
			}
		}
		
        //주의 : 2번과 3번 중 하나만 사용하자.
        
		//2. 수평 변환 수행(오른쪽으로 돌리기)
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N / 2; j++) { //절반만 변경하므로
				int temp = map[i][j];
				map[i][j] = map[i][N - j - 1];
				map[i][N - j - 1] = temp;
			}
		}
		//3. 수직 변환 수행(왼쪽으로 돌리기)
		for(int j = 0; j < N; j++) {
			for(int i = 0; i < N / 2; i++) {
				int temp = map[i][j];
				map[i][j] = map[N - 1 - i][j];
				map[N - 1 - i][j] = temp;
			}
		}
		
		
		//결과
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				System.out.print(map[i][j]+"\t");
			}
			System.out.println();
		}
	}

}