48. Rotate Image

문제

풀이

아이디어

시계방향 90도 회전 시 [i][j]의 원소는 [j][n-1-i]로 이동한다는 규칙을 발견할 수 있다.

이 규칙을 따라가면 4개의 위치가 하나의 사이클을 이룬다:

[i][j] → [j][n-1-i] → [n-1-i][n-1-j] → [n-1-j][i] → [i][j]

따라서 temp 변수 하나로 4개 위치를 교환하면 추가 공간 없이 in-place 회전이 가능하다.

순환 교환의 시작점 (i, j) 범위는 다음과 같다:

i: 0 ~ n/2 - 1 (행렬의 상단 절반)
j: i ~ n-2-i (각 행에서 이미 처리된 열 제외)

코드

function rotate(matrix: number[][]): void {
  // 시계방향으로 90도 돌려야 함...
  // [i][j] => [j][n-1-i] 이런 규칙이 보임.
  // [0][0] => [0][n-1]
  // [0][n-1] => [n-1][n-1]
  // [n-1][n-1] => [n-1][0]
  // [n-1][0] => [0][0]
  const n = matrix.length;
  for (let i = 0; i <= Math.floor(n / 2) - 1; i++) {
    for (let j = i; j <= n - 2 - i; j++) {
      let temp = matrix[i][j];
      matrix[i][j] = matrix[n - 1 - j][i];
      matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
      matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
      matrix[j][n - 1 - i] = temp;
    }
  }
}

시간 / 공간 복잡도

시간 복잡도: O(n^2) - 행렬의 모든 원소를 한 번씩 순환 교환
공간 복잡도: O(1) - 임시 변수 하나만 사용하여 in-place 처리

여담

이거 20분만에 풀어야 하는 문젠데 (Codesignal 3번 계열 문제) 무슨 40분이나 걸렸다. 시뮬레이션 문제를 좀 연습해야겠다...