68일차 - 2차원 배열 회전 (알고리즘)

블로그를 쓰면서 처음으로 알고리즘 문제 정리를 해볼까 한다.

문제 : 2차원 배열 M * N 배열을 시계 방향으로 회전시키는 함수를 만들어라. (빈 배열을 입력 받은 경우, 빈 배열을 리턴한다.)
이 함수는 첫 번째 인자로 2차원 배열을 받고 두 번째 인자로 회전한 횟수 를 받는다.

우선 한 번 회전할때 마다 배열의 index들이 어떻게 변하는지 알아야한다.
시각적으로 이해하기 쉬운 3 * 3배열을 우선 만들어본다.

여기서 index의 첫 번째는 row index이고 두 번째는 column index이다.

3 * 3	회전	이전
[0][0]	[0][1]	[0][2]
[1][0]	[1][1]	[1][2]
[2][0]	[2][1]	[2][2]

기본 배열은 이런 식으로 생성될 것이다.

3 * 3	회전	이후
[2][0]	[1][0]	[0][0]
[2][1]	[1][1]	[0][1]
[2][2]	[1][2]	[0][2]

그리고 위와 같이 바뀔 것이다.

index를 살펴보면 회전 이후 column index는 회전 이전 row index인 것을 알 수 있다.

그리고 회전 이후 row index는 회전 이전 최대 column index에서 회전 이전의 column index를 뺀 값임을 알 수 있다.

result[row][col] = matrix[matrix.length - 1 - col][row]

시계 방향으로 한번 회전 했을때를 Java Script로 표현하면

function turnMatrix(matrix, 1) {
  
  // 예외 규칙을 먼저 명시
  if (matirx.length === 0) return [];

  // 답을 출력할 배열
  let result = [];
  
  // 배열을 회전 시킴
  for (let row = 0; row < matrix[0].length; row++) {
    result[row] = [];
    for (let col = 0; col < matrix.length; col++) {
      result[row][col] = matrix[matrix.length - 1 - col][row]
    }
  }

  return result;
}

이렇게 표현 할 수 있다.

그러면 여러번 회전하는 2번째 인자가 1이 아닐때는 어떻게 해야 될까?
나는 재귀함수로 문제를 풀었다.

function turnMatrix(matrix, k) {

  if (matrix.length === 0) return [];

  let result = [];

  for (let row = 0; row < matrix[0].length; row++) {
    result[row] = [];
    for (let col = 0; col < matrix.length; col++) {
      result[row][col] = matrix[matrix.length - 1 - col][row]
    }
  }

  // 여기에 재귀함수를 넣음으로써 k번 만큼 회전시킨다
  if (k !== 1) {
    return rotateMatrix(result, k - 1)
  }

  return result;
}

이렇게 재귀 함수를 넣으면 2차원 배열을 k번 회전시킬 수 있다.