[JS 알고리즘] Toy 22 - rotateMatrix

해당 문제는 코드스테이츠의 Toy problem을 출처로 합니다.

문제

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

    Advanced

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

입력

인자 1 : matrix

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

출력

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

 

문제풀이

N*M

(가로N, 세로M으로 가정하여 구현했다)

직사각형 행렬은 회전시 크기가 달라지기 때문에 결과배열의 크기를 미리 지정하여 초기화하는 방법은 비효율적인 부분이 크다.

따라서 결과를 담을 이차원 배열을 빈배열로 생성하고 값을 넣는 방식으로 for문 사용을 줄이려고 했다.

 

N*M & K번 회전

90도(1번), 180도(2번), 270도(3번), 360도(4번) 각각의 회전마다 특정 값의 좌표 변화 규칙을 찾아야 한다.

실수를 줄이기 위해 간단한 예시를 직접 적어가면서 규칙을 찾았다.

규칙은 아래와 같다. 남색으로 표시한 것이 회전별 규칙이다.

원본 행렬의 특정값의 행 좌표를 row, 열 좌표를 col 이라고 하고, 해당 값의 회전 후 좌표의 행을 row', 열을 col'이라고 해보자.

위 그림에서 알 수 있듯, 시계방향 90도로 1번 회전할 경우 좌표의 변화 식은 row' = col, col' = M-row 이다.

1) row'=col 

회전 후의 행row’ 값은 회전 전의 col값과 같다. 이는

2) col=row'

회전 전의 열col 값은 회전 후의 행row’와 같다는 말이기도 하다.

 

 어떻게 쓰나 둘은 논리적으로 같지만, 나는 이 예제에서 회전 전의 행열 좌표(2))를 기준으로 구하는 방식으로 정리했다. 이유는 우리가 회전 후의 결과 배열(result)를 for문을 통해 채울 것이기 때문이다.

 

for문을 통해 채울 경우 result배열은 0행부터 n행까지

result[0][0...n]

result[1][0...n]

...

result[n][0...n]

순으로 값을 채워넣게 될 것이다.

 

 즉, 회전 후의 결과배열에 들어갈 값은 위에서 구한 공식대로 회전 전의 행렬의 좌표를 조작해서 구할 수 있다.

공식을 사용할때, 대입해서 풀 수 있는 주어진 좌표 인덱스는 회전 후의 결과 행렬의 좌표다. (예: result[0][0])

그러므로 찾아야하는 것은 이와 대응되는 회전 전의 행렬 좌표, 그리고 그 좌표에 저장된 값이다. 이때문에 row’=col 이 아니라, col=row’ 와 같이 회전 전의 좌표를 구하는 방식으로 정리를 해둔 것이다.

 

가로의 길이(M)가 2이고, 세로의 길이(N)가 3인 2*3크기의 행렬(matrix)

[ [1,2],

  [3,4],

  [5,6] ]

이 있고, 이 행렬이 시계방향 90도로 1번 회전한 결과를 구한다고 가정해보자.

 

 회전 결과 행렬(result)은 N*M인 3*2크기의 행렬이 될것이고, (0,0)에 위치한 값은 위의 공식에 대입해서 구해지는 좌표의 값이다.

         ( 1회 회전시 좌표 변화 공식: col=row', row=N-col')

result의 (0,0)에 대응되는 원본 행렬 matrix의 좌표는 row = N-col'-1 = 3-0-1 = 2, col = row' = 0

         (M은 원본행렬의 가로 길이, 배열의 인덱스는 0~M-1이므로 구현단계에서는 길이에서 -1 해줘야함)

즉, result[0][0]은 matrix[2][0]의 값과 같다는 결과를 도출할 수 있다. 

 

1번 회전한 결과는 아래와 같으므로, 도출해낸 공식과 결과값이 맞다는 것을 알 수 있다.

[ [5,3,1],

   [6,4,2] ]

     * result[0][0] == matrix[2][0]

 

이후 2번 회전, 3번 회전도 이와 같이 미리 구해둔 공식을 대입하는 방식으로 구현하면 된다.

 

작성한 코드 (Javascript 구현)

/***************** Advanced - K번씩 회전 조건 추가 ***************/
const rotateMatrix = function (matrix, rotation = 1) {
  if (matrix.length === 0) return [];

  // 입력받은 행렬의 가로(열):M 세로(행):N 길이
  const M = matrix[0].length;
  const N = matrix.length;

  // 90도, 180도, 270도, 360도 회전 구별 위함
  const K = rotation % 4;

  let result = [];

  // Advanced: m*n -> n*m , k번 회전 구현
  if (K === 0) return matrix;
  if (K === 2) {
    for (let row = 0; row < N; row++) {
      result[row] = [];
      for (let col = 0; col < M; col++) {
        result[row][col] = matrix[M-row-1][N-col-1];
      }
    }
  }
  else {
    for (let row = 0; row < M; row++) {
      result[row] = [];
      for (let col = 0; col < N; col++) {
        if (k === 1)
          result[row][col] = matrix[N-col-1][row];
        if (k === 3)
          result[row][col] = matrix[col][M-row-1];
      }
    }
  }

  return result;
};

 result 배열에 값을 넣을때 push를 사용할 수도 있겠지만, 공식과 잘 대응되는지 한눈에 확인하기에는 해당 인덱스를 명시하여 값을 저장하는 방식이 더 낫겠다는 판단을 했다. 

 

 

레퍼런스 코드 (Javascript 구현)

const rotateMatrix = function (matrix, rotateNum = 1) {
  // rotateNum 이 0일 수 있으므로 아래와 같은 초기화는 지양해야 함
  // rotateNum = rotateNum || 1
  const N = matrix.length;
  // 빈 배열을 입력받을 수 있다.
  const M = matrix[0] && matrix[0].length;

  rotateNum = rotateNum % 4;
  // 회전하지 않는다.
  if (rotateNum === 0) return matrix;

  const rotated = [];
  // 홀수번 회전 시 M x N, 짝수번 회전 시 N x M
  const RC = rotateNum % 2 === 1 ? [M, N] : [N, M];

  for (let row = 0; row < RC[0]; row++) {
    rotated[row] = [];
    for (let col = 0; col < RC[1]; col++) {
      if (rotateNum === 1) rotated[row][col] = matrix[N - col - 1][row];
      else if (rotateNum === 2)
        rotated[row][col] = matrix[N - row - 1][M - col - 1];
      else rotated[row][col] = matrix[col][M - row - 1];
    }
  }

  return rotated;
};

 

배운 점

 레퍼런스 코드를 확인해보니, 내가 작성한 코드와 로직은 같았다.

다만, 회전 별 결과 배열의 크기가 달라지는 부분을 나는 단순히 if문으로 나눴다면, 레퍼런스 코드에서는 M*N 크기와 N*M 크기를 배열로 표현하여 접근하는 방식을 사용했다. 내 코드에서 홀수 회전과 짝수 회전 마다 겹치는 규칙을 배열을 활용해서 리팩토링하면 레퍼런스 코드가 되는 것 같다. 보다 깔끔하고 코드의 길이를 줄일 수 있는 좋은 방법인 것 같다.

 

규칙적인 반복이 있을 때 배열을 마치 포인터 메모처럼 사용할 수도 있다는 것을 기억하자!

테스트 통과에서 끝내지 않고 코드 가독성과 효율성을 높이려고 계속해서 노력해야한다.

"남의 코드를 많이 볼수록 배우는 것도 더 많아진다" 는 말을 실감 중이다.

 

 

 

---

자꾸만 && 와 || 를 알고리즘 풀이에서는 까먹고 사용하지 않게 되어 노션 말고 티스토리에도 정리해두려고 한다.

기억하면 좋은 JS 연산자 문법

논리 연산자 코드 총 3가지

연산자	표기법	구문	구문 치환	설명
논리 AND	&&	example1 && example2	NOT example1	example1 이 true 인 경우 example2 을 반환하고 그렇지 않은 경우 example1을 반환
논리 OR	||	example1 || example2	example1 OR example2	example1 이 true 인 경우 example2 을 반환하고 그렇지 않은 경우 example1을 반환
논리 NOT	!	!example1	NOT example1	example1 OR example2

 

 

---

다른 사람의 코드가 더 궁금해서 찾아봤다.

https://velog.io/@ajt1097/AlgorithmToy-Problem-22

나의 코드와 레퍼런스 코드처럼 한 번에 좌표를 찾는 방법도 있지만, 시계방향으로 90도 1회 회전하는 로직을 함수로 따로 빼서 담고, 이를 입력받은 회전 횟수만큼 호출 및 실행시켜주는 방법도 있었다. 회전 횟수가 급격하게 커진다면 부담이 갈 수 있는 방식인 것 같지만, 생각하지 못한 접근 방법이어서 함께 기록해둔다.