알고리즘 12 : 배열 회전

 

rotateMatrix

문제

2차원 N x N 배열을 시계 방향으로 90도 회전시킨 배열을 리턴해야 합니다.

입력

인자 1 : matrix

• 가로 길이(matrix[i].length)와 세로 길이(matrix.length)가 모두 N인 2차원 배열
• matrix[i][j]는 number 타입

출력

• 2차원 배열을 리턴해야 합니다.

입출력 예시

const matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
];
console.log(matrix[0][0]); // --> 1
console.log(matrix[3][2]); // --> 15

const rotatedMatrix = rotateMatrix(matrix);
console.log(rotatedMatrix[0][0]); // --> 13
console.log(rotatedMatrix[3][2]); // --> 8

힌트

• 컴퓨터 과학에서 행렬은 '행'의 길이인 m과 '열'의 길이인 n의 곱으로 표현됩니다. m X n 행렬은 아래와 같이 2차원 배열로 구현할 수 있습니다. (행렬의 요소를 전부 initVal로 초기화)

const matrix = [];
for(let row = 0; row < m; row++>) {
  matrix.push(Array(n).fill(initVal))
}

이때 matrix[i][j]는 '행(세로축)을 기준으로 i만큼 아래에 있고 열(가로축)을 기준으로 j만큼 옆에 있다.`를 뜻합니다. 이 방식은 기하학에서 좌표 평면 위의 한 점을 나타낼 때 (x, y), 즉 가로축을 먼저 표기하고 세로축을 다음에 표기하는 방식과는 다릅니다. 그래프를 인접행렬로 구현할 때, 이 점을 주의하셔야 합니다.

Advanced

• 세로와 가로의 길이가 각각 M, N인 2차원 M X N 배열을 시계방향으로 90도씩 K번 회전시킨 배열을 리턴해 보세요. 회전수가 두 번째 입력으로 주어집니다.

코드

 

const rotateMatrix = function (matrix,K=1) {
  if(matrix.length===0)return []
  // TODO: 여기에 코드를 작성합니다.
 
  let n = matrix.length;
  let m = matrix[0].length;

  let arr = new Array(m).fill([]).map(el=>new Array(n).fill())


  
    for(let i = 0;i<n;i++){
      for(let j = 0;j<m;j++){
        arr[j][n-i-1] = matrix[i][j]
      }
    }
  
    if(K===1) return arr
    return rotateMatrix(arr,K-1)
  
  // if(K>1)return rotateMatrix(arr,K-1)
  // return arr
  
};

설명

다음은 배열을 회전시키는 코드이다.

let n = matrix.length;
let m = matrix[0].length;

let arr = new Array(m).fill([]).map(el=>new Array(n).fill())
    
    
    for(let i = 0;i<n;i++){
      for(let j = 0;j<m;j++){
        arr[j][n-i-1] = matrix[i][j]// 시계 방향 90도
        arr[n-j-1][i] = matrix[i][j]// 반시계 방향 90도
        arr[n-i-j][j] = matrix[i][j]// 상하반전
        arr[i][n-j-i] = matrix[i][j]// 좌우반전
      }
    }

 

 

마지막 리턴 부분

const rotateMatrix = function (matrix,K=1) {
.
.
.
    //선언부분에서 K를 number로 지정했기에 가능하다.
    //K를 number로 지정하지 않으면 K가 undefined일때의 return rotateMatrix(arr,NaN)이 계속 호출되어
    //Maximum call stack size exceeded 가 발생한다.
    if(K===1) return arr
    return rotateMatrix(arr,K-1)
 } 
 //K를 number로 지정하지 않았을때는 아래와 같이 작성한다.
  // if(K>1)return rotateMatrix(arr,K-1)
  // return arr