498. Diagonal Traverse

Leetcode 498번 풀이

문제

Diagonal Traverse

풀이

아이디어

대각선 이동 방향을 up(↗)과 down(↙) 두 가지로 나누어 시뮬레이션한다.

• up: [y-1, x+1] 방향으로 이동하다 경계를 벗어나면 turn으로 다음 시작 위치 계산
• down: [y+1, x-1] 방향으로 이동하다 경계를 벗어나면 turn으로 다음 시작 위치 계산

turn 은 방향에 따라 우선순위가 다르다:

• up에서 벗어날 때: 오른쪽(x+1)이 가능하면 오른쪽, 아니면 아래(y+1)
• down에서 벗어날 때: 아래(y+1)가 가능하면 아래, 아니면 오른쪽(x+1)

코드

type MoveAction = (y: number, x: number) => [number, number];
type Moves = {
  move: MoveAction;
  turn: MoveAction;
};
type Direction = 'up' | 'down';

function findDiagonalOrder(mat: number[][]): number[] {
  // 행렬로 정말 별걸 다 한다는 생각이 듭니다...
  const [m, n] = [mat.length, mat[0].length];
  // move: 말그대로 움직이기, turn: 방향 전환
  const moves: Record<Direction, Moves> = {
    up: { move: (y, x) => [y - 1, x + 1], turn: (y, x) => (x + 1 < n ? [y, x + 1] : [y + 1, x]) },
    down: { move: (y, x) => [y + 1, x - 1], turn: (y, x) => (y + 1 < m ? [y + 1, x] : [y, x + 1]) },
  };

  // 움직이기..
  let dir: Direction = 'up';
  const answer = [];
  let [y, x] = [0, 0];
  while (answer.length < m * n) {
    answer.push(mat[y][x]);
    let [ny, nx] = moves[dir].move(y, x);
    if (ny < 0 || ny >= m || nx < 0 || nx >= n) {
      // 방향 전환이 필요한 상황!
      [ny, nx] = moves[dir].turn(y, x);
      dir = dir === 'up' ? 'down' : 'up';
    }
    [y, x] = [ny, nx];
  }

  return answer;
}

시간 / 공간 복잡도

• 시간 복잡도: O(m * n) — 행렬의 모든 원소를 한 번씩 순회
• 공간 복잡도: O(1) — 결과 배열 외 추가 공간 사용 없음

여담

시간복잡도는 더 이상 최적화할 방법이 없어 보이긴 한데, 실행 시간을 보면 18ms로 꽤 느리게 나왔다. 1ms로 실행되는 솔루션을 보니 내 코드에서 함수 실행이라던가, 배열 구조분해할당 같은 부분에서 오버헤드가 발생하는 것 같다. 코드 가독성은 내 코드쪽이 좀 더 좋은 것 같긴 한데 실행 시간이 중요한 상황이라면 이런 부분도 최적화하는 게 좋을 것 같다.