Leetcode Rotate Image in Javascript

6588 단어 algorithmalgorithm

문제

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

접근

문제의 제목과 사진만 보면 새로운 배열을 생성하고 원래 배열을 탐색하며 새 배열을 채워나가서 쉽게 문제를 풀 수 있다.

1열의 값이 거꾸로 되서 1행의 값이 되어주면 간단하게 해결이 가능했다 하지만 문제의 제한 조건인

DO NOT allocate another 2D matrix and do the rotation.

이 부분을 확인하면 새로운 배열을 위해 메모리를 allocate하지 말라고 되어있다. 따라서 원래 배열을 고쳐가야한다.

위 사진을 자세히보자.
그리고 먼저 원래 배열을 대칭이 되도록 배열내 원소를 바꾸어보자. 그러면 배열이

[1,4,7] , [2,5,8], [3,6,9]

이렇게 된다. 그 다음 각 배열의 원소를 뒤집어주면

[7,4,1], [8,5,2], [9,6,3]

정답 배열이 된다. 정답 코드는 아래와 같다.

var rotate = function(matrix) {
    const size = matrix.length;
    let start = 0;   
    
    // transpose
    for(let i=0; i<size; i++){
        for(let j=start; j<size; j++){
            if(i !== j){
                let temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        start++;
    }
    
    // reverse
    for(let i=0; i<size; i++){
        for(let j=0; j<size/2; j++){
            let temp = matrix[i][j];
            matrix[i][j] = matrix[i][size-j-1];
            matrix[i][size-j-1] = temp;
        }
    }
    
    return matrix;
};

좋은 웹페이지 즐겨찾기