[LeetCode] 48 Rotate Image JavaScript

문제 링크

Rotate Image - LeetCode

 

문제 유형

2차원 배열

 

문제 풀이

이 문제는 이미지를 나타내는 2차원 행렬이 2차원 배열로 주어지고, 이를 시계방향으로 90도 돌렸을 때의 배열을 반환하는 문제이다.

처음 n x n 행렬의 인덱스를 oldX, oldY라 하고 90도 돌린 행렬의 인덱스를 newX, newY라고 할 때, 인덱스 간의 관계는 다음과 같다.

newX = -oldY + (n - 1)
newY = oldX

 

그리고 n이 짝수인 행렬과 홀수인 행렬을 나눠서 생각해보자.

• n이 짝수: x의 인덱스가 0 ~ (n / 2 - 1)인 숫자들과 y의 인덱스가 0 ~ (n / 2 - 1)인 숫자들을 시작 매트릭스로 잡고 90도 돌리면 같은 색깔에 위치한 숫자들이 회전한다.
• n이 홀수: x의 인덱스가 0 ~ ((n + 1) / 2 - 1) 인 숫자들과 y의 인덱스가 0 ~ (n / 2 - 1)인 숫자들을 시작 매트릭스로 잡고 90도 돌리면 같은 색깔에 위치한 숫자들이 회전한다.

 

따라서 코드로 구현하려면 다음과 같이 접근해야 한다.

1. 이중 for문을 돌려서 매번 시작 지점이 90도 회전하면서 같이 회전하게 될 위치들을 구한다.
  예제에서 1을 시작 지점으로 잡으면 다음과 같다.

숫자	전	후
1	(0, 0)	(0, 2)
3	(0, 2)	(2, 2)
9	(2, 2)	(0, 2)
7	(0, 2)	(0, 0)

2. 1을 통해 회전하면 각 행렬의 값이 어디에 위치하는지를 알 수 있게 된다. 따라서 회전한 후의 위치에 회전하기 전의 위치를 넣어주면 회전했을 때의 배열을 in-place하게 나타낼 수 있다.
이때, (newX1, newY1)에  (newX3, newY3)의 값이 들어가게 되므로 시작 지점의 값을 임시 변수에 담아 시작 지점(x, y)의 값을 기억한다. 

 

접근 방법을 이해하는데 오랜 시간이 걸렸지만 회전 전/후 인덱스 간의 관계를 찾고 결과적으로 각 숫자가 회전하면서 위치가 어떻게 변하는지 생각해보는 좋은 접근법이라는 생각이 들었다. 좋은 문제인 것 같아 잘 기억해야겠다,,

 

코드

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const N = matrix.length;
    const xLen = Math.floor((N + 1) / 2);
    const yLen = Math.floor(N / 2);
    
    for (let y = 0; y < yLen; y++) {
        for (let x = 0; x < xLen; x++) {
        	// 시작 지점과 같이 회전하는 인덱스의 위치를 찾는다
            const [newX1, newY1] = getNewIdx(N, x, y);
            const [newX2, newY2] = getNewIdx(N, newX1, newY1);
            const [newX3, newY3] = getNewIdx(N, newX2, newY2);
            
            // 회전한 후의 위치로 변경한다
            const temp = matrix[y][x];
            matrix[y][x] = matrix[newY3][newX3];
            matrix[newY3][newX3] = matrix[newY2][newX2];
            matrix[newY2][newX2] = matrix[newY1][newX1];
            matrix[newY1][newX1] = temp;
        }
    }
    return matrix;
};

const getNewIdx = (n, oldX, oldY) => {
    const newX = -oldY + n - 1;
    const newY = oldX;
    return [newX, newY];
}

 

참고

https://www.youtube.com/watch?v=4-y6eGUY-sI