리트코드 - 48. Rotate Image

리트코드 - 48. Rotate Image

출처 - https://leetcode.com/problems/rotate-image/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

n x n 2D 행렬로 표현된 이미지가 주어집니다. 이 이미지를 시계 방향으로 90도 회전시켜야 합니다. 이미지를 제자리에서 회전시켜야 하므로, 입력된 2D 행렬을 직접 수정해야 합니다. 다른 2D 행렬을 할당하여 회전시키면 안 됩니다.

 

풀이코드

class Solution {
    public void rotate(int[][] matrix) {
        int N = matrix.length;
        int temp = 0;
        int startIdx = 0;
        int count = N / 2;
        while (count > 0) {
            int first = startIdx;
            int last = N - 1 - first;
            for (int i = first; i < last; i++) {
                // 시작 위치
                int offset = i - first;

                // 임시 배열
                temp = matrix[first][i];

                // 반시계 방향으로 회전
                matrix[first][i] = matrix[last - offset][first];
                matrix[last - offset][first] = matrix[last][last - offset];
                matrix[last][last - offset] = matrix[i][last];

                // 마지막은 임시배열에서 값을 대입
                matrix[i][last] = temp;
            }
            startIdx++;
            count--;
        }
    }
}

코드설명

주어진 조건에서 2차원 배열을 만들지 말고 회전하라고 하였으므로 다른 방법을 떠올려야 한다.

배열을 회전했을 때를 그려보면 빨간색 영역은 빨간색 영역끼리, 초록색 영역은 초록색 영역끼리 회전한다.

같은 색의 영역끼리만 이동하고, 색이 다른 영역은 서로간 영향을 미치지 않으므로 각 영역에서의 규칙을 만들면 된다.

마치 껍질 혹은 레이어라고도 볼 수 있을 것 같다.

 

규칙만 놓고 보면 매우 간단하다. 위쪽줄이 오른쪽 줄로 가고, 오른쪽 줄이 아래, 아래줄이 왼쪽, 왼쪽이 위쪽 줄로 간다.

그렇지만 단순하게 이렇게 생각해서 배열의 원본 자체를 수정해버리면 이동과정에서 값이 엉망으로 뒤엉켜버린다.

왜냐하면 대입할 배열의 값은 아직 이동하기 전이기 때문에 이동할 값 대신 덮어씌운 값이 또 이동하게 된다.

 

따라서, 배열을 바꾸기전에 원본값을 임시로 저장한 다음, 덮어씌우면 된다.

 

이를 위해서 임시값을 하나 만들고 저장해준다.

1은 4의 위치로 갈것이다.

그렇지만 1을 저장해 두었다면, 이 값을 4로 이동시키는 것이 아니라 거꾸로 이동해야한다.

이렇게 역으로 이동해주어야 된다.

순차적으로 반시계 방향으로 16을 13으로, 4를 16위치에 이동시킨다음,

마지막 4의 위치에 있던 곳에 임시값으로 저장했던 1을 대입해주면 일단 첫번째 값 돌리기는 끝났다.

두번째는 맨 윗줄에서 하나 오른쪽으로 이동후 진행해주면 되는데 인덱스를 잘 고려해줘야 한다.

 

먼저 첫번째 값의 좌표(인덱스)는 (0,0)이고, 순회 이후 다음 값은 오른쪽으로 한 칸 이동하므로 (0, + 1)이 된다.

두번째로는 제일 왼쪽 아래(제일 가로 끝, 0)의 순회 이후 윗 행의 값이 되므로 (제일 가로 끝 - 1, 0) 이 된다.

이런 방식으로 세번째는 (끝,끝 - 1) 네번째는 (0 + 1, 끝) 이 될 것이다.

 

이것을 코드로 표현하면 아래와 같이 될 것이다.

temp = matrix[0][i];

// 두번째 값
matrix[0][i] = matrix[last - i][0];
// 세번째 값
matrix[last - i][0] = matrix[last][last - i];
// 네번째 값
matrix[last][last - i] = matrix[i][last];

// 마지막 값
matrix[i][last] = temp;

 

last는 배열의 제일 끝 인덱스를 나타내고, i값을 늘려 반복문을 돌려주면 된다.

순회는 마지막 직전값 까지 하게 될 것이다.

마지막 값은 이미 1에서 -> 4 로 이동된 값일 것이기 때문이다.

또한 중요한 것은 이 코드는 제일 바깥쪽을 돌 때만 유효하다는 것이고, 다음 안쪽을 돌 때에는 값을 수정해줘야 한다는 것이다.

 

안쪽 칸은 가로 세로 한 칸씩 총 두 칸이 줄어들 것이다.

예를 들어 제일 바깥쪽이 5x5였다면, 안 쪽은 3x3이 될 것이기 때문이다.

 

동작을 먼저 확인해보면 (0,0)으로 시작했던 인덱스는 (+1, +1)이 되고 y값이 1씩 늘어나게 된다.

다음으로 (last, 0) 으로 시작했던 인덱스는 (last - 1, +1) 이 될 것이고,  x값이 1씩 줄어들게 된다.

마찬가지로 (last, last - 1)이었던 인덱스는 (last - 1, last -1 -1)이 될 것이고, y값이 1씩 줄어들게 된다.

마지막으로 (0, last) 였던 인덱스는 (+1, last - 1)이 되고 , x값이 1씩 늘어나게 된다.

 

이를 해결하기 위해서 0과 last를 조금 더 세분화해야 한다.

 

먼저 for문이 i = 0 이 아니라 first = 0으로 두고, i = first로 시작하게 만들고 last 까지만 순회하게 만든다.

그리고 last = N - 1 - first로 정의하면 first가 하나 늘어날 때 last도 -1 이 되므로 반복문에서 -2가 줄어 원하는 길이 순회가 가능하다.

 

다음으로 처음에 정의했던 last는 배열의 길이였다면, 지금은 last 값 자체가 first에 의해 하나 줄었다.

따라서 순회하는 각 끝 값은 last - (i - first)으로 두며 순회하면 i값에 따라 원하는 값을 순회할 수 있다.

 

코드의 가독성을 위해 i - first를 offset으로 두고, last - offset으로 두면 코드가 조금 더 구조적이게 된다.

int first = startIdx;
int last = N - 1 - first;
for (int i = first; i < last; i++) {
    // 시작 위치
    int offset = i - first;

    // 임시 배열
    temp = matrix[first][i];

    // 반시계 방향으로 회전
    matrix[first][i] = matrix[last - offset][first];
    matrix[last - offset][first] = matrix[last][last - offset];
    matrix[last][last - offset] = matrix[i][last];

    // 마지막은 임시배열에서 값을 대입
    matrix[i][last] = temp;
}
startIdx++;

변경된 부분이 위와 같은 코드이고, 이렇게 이동시키면 배열 안쪽까지 하나씩 회전해서 옮길수 있다.

 

몇 번 옮기는지는 귀납법으로 계산했는데, 4x4 라면 2번, 5x5이어도 2번(제일 안쪽은 1개짜리) 6x6 는 3번 ... 식이어서 count = N / 2로 두었고, while문으로 count를 감소하였다.

 

시간복잡도 - O(N^2)

공간복잡도 - O(N^2)

 

초기 생각한 흐름

처음에는 각 껍데기(?) 배열을 통째로 임시배열에 저장하고 각각 for문을 돌렸는데, for문을 네번이나 돌려야해서 비효율적이었다.

for문을 합치는 과정에서 원소를 하나씩 옮기는 방법을 발견하여 코드로 적용했고 위와같은 코드를 적용할 수 있었다.

 

정리

배열을 회전하는 방법