48. Rotate Image

문제링크: https://leetcode.com/problems/rotate-image/


주어진 배열을 추가적인 배열 사용 없이 90도 회전시키는 문제다.

Solution

Swap quarter block

90도 회전은 4개의 위와 같은 방법으로 4등분한 블록들을 재배치하는 방식으로 구현할 수 있다.

Algorithm

• 반복할 블록을 위한 인덱스를 지정한다.
• 짝수길이, 홀수길이의 매트릭스를 모두 만족하기 위해 row는 가로줄을 미포함, col은 가로줄을 포함해 사각 블록을 지정한다.
• 블록에서 하나의 원소를 선택해 4블록에서 swap을 한다.

var rotate = function(matrix) {
    // 4등분하고 왼쪽 위의 블록을 4번씩 반복
    // [a, b] => [b, n - 1 - a]
    const n = matrix.length;
    const quarter = (n - 1) / 2; 
    for (let i = 0; i < quarter; i++) { // 가운데 줄 미포함
        for (let j = 0; j < n / 2; j++) { // 가운데 줄 포함
            // 구조분해 할당 스왑으로 직관적으로
            [matrix[j][n - 1 - i],
             matrix[n - 1 - i][n - 1 - j],
             matrix[n - 1 - j][i],
             matrix[i][j]] 
                = [matrix[i][j],
                  matrix[j][n - 1 - i],
                  matrix[n - 1 - i][n - 1 - j],
                  matrix[n - 1 - j][i]];
        }
    }
};