[Leetcode] 48. Rotate Image - JS

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

 

 

 

 

1. 문제 분석

문제분석
--------------------
- n x n 2차원 배열이 주어지면 이를 제자리에서 90도 시계 방향으로 돌려라.
- 또 다른 2차원 배열에 할당하지 말라 !

제한조건
--------------------
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000

 

2. 접근 방법

접근방법 Transpose(전치) + Reverse(좌우반전)
--------------------
1. 행과 열을 대각선을 기준으로 swap 한다.
2. 행의 요소를 역순정렬한다.

 

 

 

3. 코드

var rotate = function(matrix) {
    const n = matrix.length;

    // 1. 행열을 대각선 기준으로 swap
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }

    // 2. 각 행을 역순정렬
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n^2)

- 공간복잡도: O(1)

 

90도로 돌리기 위해 어떤 과정을 해야하는지 생각해보았다. 처음에 내가 생각한 방법은 matrix[i][j] 위치가 matrix[j][n - i - 1] 로 이동하는 것을 알게되었는데, 이렇게 되면 사각형의 배열이 90도를 돌아가야하므로 총 4번의 과정을 해야한다. 1회 이동은 계산이 가능한데, 4회까지 이동하면서 swap 할 방법이 떠오르지 않았다.

 

다른 방법이 떠오르지 않아 GPT에게 물어봐서 문제를 해결했다.

GPT한테 물어보니, 내가 접근한 방법으로 원래 좌표 (i, j)는 회전 후 (j, n - i - 1)로 이동하는 것도 가능하지만

반복적으로 직접 계산하는 방법 대신 더 간단한 해결책을 제시했다.

 

Transpose(전치) 과정을 통해 행과 열을 바꾼다. 이를 통해 대각선 기준으로 대칭이 되도록 바꾼다.

대각선 축을 기준으로 좌표 교환을 하는 것은 회전의 기본 단계와 일치한다.

 

Transpose를 통해 좌표의 대칭 변환은 완료 되었지만 좌우 반전이 필요하므로, 각 행을 뒤집어 좌우 반전을 시켜 90도 회전을 완성시킨다.

 

행열을 회전시키는 방법으로 Transpose + Reverse 방법이 제자리에서 회전시키는 일반적이고 효과적인 방법이므로 패턴을 반복 연습하여 익숙해져야겠다.