Today
-
Yesterday
-
Total
-
  • 01. 이차원 배열 회전
    CS/Data Structure & Algorithm 2021. 4. 6. 12:56

    코딩테스트 문제를 풀다보면 이차원 배열을 시계방향으로 90도 회전할 일이 종종 있다.

    출처: https://shoark7.github.io/programming/algorithm/rotate-2d-array

     

    00 > 02 01 > 12 02 > 22
    10 > 10 11 > 11 12 > 21
    20 > 00 21 > 10 22 > 20

    위 표를 자세히 보면 A(i, j)에서 90도 회전을 하면 A(m - 1 - j, i)로 넘어간다는 것을 확인 할 수 있다.

    해서 이중 for문을 이용해 간단하게 구현할 수 있을 줄 알았는데 array deep copy를 하는 데에서 헤메고 말았다.

     

    분명히 [...arr]로 Deep Copy를 했다고 생각했는데 arr를 변경하자 복사한 배열인 tmpArr가 함께 변경되는 것이었다.

    이중 배열이다 보니 안의 배열들은 그대로 shallow copy가 되기 때문이었고, 결국 배열의 각 행을 탐색해 들어가며
    행별로 deepcopy를 해주어야 했다.

    //배열을 회전하는 함수
    function rotate(arr) {
        const tmpArr = [...arr];
        const N = arr.length;
    
    	//이중배열 Deep Copy
        for (let i = 0 ; i < N ; i ++) {
            tmpArr[i] = [...arr[i]];
        }
        
        //이중배열 시계방향으로 90도 회전시키기!
        for (let i = 0 ; i < N ; i ++) {
            for(let j = 0 ; j < N ; j ++) {
                let y = j;
                let x = N - 1 - i;
                
                if (x < 0) {
                    x = M - 1;
                }
                arr[y][x] = tmpArr[i][j];
            }
        }
    }

    댓글