48. Rotate Image 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

1. 자리를 로테이션 한다는 뜻은, 각 자리에서 옮길 자리가 정해져 있다는 뜻이다.
2. n이 3일 경우 예를 든다면 아래와 같다

(0,0)->(0,2)
(0,2)->(2,2)
(2,2)->(2,0)
(2,0)->(0,0)

(0,1)->(1,2)
(1,2)->(2,1)
(2,1)->(2,1)
(1,0)->(0,1)

1. 위 규칙은 n에서 멀어진 만큼으로 계산이 가능하다.

첫번쨰 루프
n=3
y축 멀어진 만큼의 거리 = i = 0
x축 멀어진 만큼의 거리 = j = 0


시작점 = (i,(i+x축 멀어진 만큼의 거리)) = (0,0)
((n-1-x축 멀어진 만큼의 거리-y축 멀어진 만큼의 거리),i)=((3-1-0-0),0)=(2,0)
((n-1-y축 멀어진 만큼의 거리),(n-1-x축 멀어진 만큼의 거리-y축 멀어진 만큼의 거리))=((3-1-0),(3-0-1-0))=(2,2)
(((i+x축 멀어진 만큼의 거리)),(n-1-y축 멀어진 만큼의 거리))=((0+0),(3-1-0))=(0,2)

두번쨰 루프
n=3
y축 멀어진 만큼의 거리 = i = 0
x축 멀어진 만큼의 거리 = j = 1


시작점 = (i,(i+x축 멀어진 만큼의 거리)) = (0,1)
((n-1-x축 멀어진 만큼의 거리-y축 멀어진 만큼의 거리),i)=((3-1-1-0),0)=(1,0)
((n-1-y축 멀어진 만큼의 거리),(n-1-x축 멀어진 만큼의 거리-y축 멀어진 만큼의 거리))=((3-1-0),(3-1-1-0))=(2,1)
(((i+x축 멀어진 만큼의 거리)),(n-1-y축 멀어진 만큼의 거리))=((0+1),(3-1-0))=(1,2)

1. 또한 반복문 역시 첫번쨰 루프는 절반만, 두번쨰 루프는 마지막을 제외한체 시작해서 맨앞쪽이 1씩 늘고 맨 뒤쪽이 1씩 줄어들어야 한다.
2. n이 3일 경우 예를 든다면 아래와 같다

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
일떄, 
(0,0) (0,1) 만 루프문에 들어가야 한다

1. n이 4일 경우 예를 든다면 아래와 같다

(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
(3,0) (3,1) (3,2) (3,3)
일떄, 
(0,0) (0,1) (0,2) (1,1) (1,2) 만 루프문에 들어가야 한다

1. 위 반복문을 설정하기 위해서 아래와 같이 루프문 횟수를 계산한다.

int i_loop = n / 2;
int j_loop = n - 2 * i - 1;

시간복잡도: O(n^2), 공간복잡도: O(1)

https://github.com/eunhanlee/leetcode_48_Rotate_Image

class Solution {
    /**
     * 주어진 2차원 배열을 시계 방향으로 90도 회전시킵니다.
     * @param matrix 2차원 배열
     */
    public void rotate(int[][] matrix) {
        // 마지막 위치 (배열의 인덱스는 0부터 시작하므로 길이에서 1을 빼줍니다)
        int lastPos = matrix.length - 1;
        // i 루프는 배열의 길이의 반만큼만 돌면 됩니다
        int i_loop = matrix.length / 2;
        for (int i = 0; i < i_loop; i++) {
            // j 루프는 마지막위치 - 현재 i의 위치 +올림
            int j_loop = lastPos - 2 * i;
            for (int j = 0; j < j_loop; j++) {
                setNewPos(matrix, i, j, lastPos);
            }
        }
    }

    /**
     * 현재 위치의 값을 시계 방향으로 90도 회전한 위치로 이동시킵니다.
     * @param matrix 2차원 배열
     * @param i 현재 위치의 행 인덱스
     * @param j 현재 위치의 열 인덱스
     * @param lastPos 배열의 마지막 인덱스
     */
    public static void setNewPos(int[][] matrix, int i, int j, int lastPos) {
        // 현재 위치 (i,j)의 값을 새로운 위치로 이동시킵니다.
        // 새로운 위치는 시계방향으로 90도 회전한 위치입니다.
        // (i,j) -> (lastPos-i-j,i) -> (lastPos-i,lastPos-i-j) -> (j,lastPos-i) -> (i,j)

        int temp = matrix[i][i + j];
        matrix[i][i + j] = matrix[lastPos - i - j][i];
        matrix[lastPos - i - j][i] = matrix[(lastPos - i)][lastPos - i - j];
        matrix[(lastPos - i)][lastPos - i - j] = matrix[i + j][(lastPos - i)];
        matrix[i + j][(lastPos - i)] = temp;
    }
}

문제해결방법2

1. 매트릭스를 90도 회전은 어렵지만, 뒤집는것은 쉬움
2. 대각선으로 뒤집고, 좌우로 뒤집으면 이는 90도 회전과 같습니다.

시간복잡도: O(n^2), 공간복잡도: O(1)

https://github.com/eunhanlee/leetcode_48_Rotate_Image

public class Solution {
    /**
     * 주어진 2차원 배열을 시계 방향으로 90도 회전시킵니다.
     * @param matrix 2차원 배열
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 대각선을 기준으로 좌우를 바꿉니다.
        for (int i = 0; i < n; i++) {
        	// j는 i부터 시작하면 됩니다. (j<i인 경우 이미 바뀌었기 때문)
            for (int j = i; j < n; j++) { 
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 각 행의 좌우를 바꿉니다.
        for (int i = 0; i < n; i++) {
        	// j는 n/2보다 작아야 합니다. (행의 중앙을 기준으로 좌우가 대칭이기 때문)
            for (int j = 0; j < n / 2; j++) { 
                int temp = 0;
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}