54. Spiral Matrix

문제

풀이

아이디어

나선형 순회는 우 → 하 → 좌 → 상 방향을 반복하며, 한 방향을 끝까지 이동하면 다음 방향으로 전환한다.

단순히 고정된 경계값(0, n-1 등)으로 방향 전환을 판단하면, 이미 소비된 행/열에 다시 진입하는 문제가 생긴다. 이를 해결하기 위해 top, right, bottom, left 4개의 경계 변수를 추가했다.

방향이 전환되는 시점은 곧 해당 변의 탐색이 완료된 시점이므로, 방향 전환과 동시에 해당 경계를 한 칸 좁힌다:

오른쪽 끝 도달 → 아래로 전환, top++
아래쪽 끝 도달 → 왼쪽으로 전환, right--
왼쪽 끝 도달 → 위로 전환, bottom--
위쪽 끝 도달 → 오른쪽으로 전환, left++

코드

function spiralOrder(matrix: number[][]): number[] {
  const answer = [];
  const [m, n] = [matrix.length, matrix[0].length];
  const moves = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]; // 순서대로 우-하-좌-상 방향 이동
  let [y, x] = [0, 0];
  let dir = 0; // 0: 오른쪽, 1: 아래쪽, 2: 왼쪽, 3: 위쪽 방향
  let [top, right, bottom, left] = [0, n - 1, m - 1, 0]; // 상, 우, 하, 좌 경계. 방향 바뀔때마다 업데이트됨

  // 모든 원소를 출력할 때 까지 반복한다.
  while (answer.length !== m * n) {
    // 현재 원소 출력
    answer.push(matrix[y][x]);
    // 이동 방향 결정 : boundary에 닿아 있으면 방향을 전환해줌.
    // boundary값도 함께 변경한다. (해당 행/열을 모두 소비했기 때문...)
    if (dir === 0 && x === right) {
      dir = 1;
      top++;
    } else if (dir === 1 && y === bottom) {
      dir = 2;
      right--;
    } else if (dir === 2 && x === left) {
      dir = 3;
      bottom--;
    } else if (dir === 3 && y === top) {
      dir = 0;
      left++;
    }
    // 다음 원소 결정
    [y, x] = [y + moves[dir][0], x + moves[dir][1]];
  }

  return answer;
}

시간 / 공간 복잡도

시간 복잡도: O(m * n) - 행렬의 모든 원소를 한 번씩 순회
공간 복잡도: O(1) - 결과 배열을 제외하면 상수 공간만 사용