766. Toeplitz Matrix

Leetcode 766번 풀이

문제

Toeplitz Matrix

풀이 1

아이디어

문제 그대로를 구현했다. 대각선이 모두 같은 원소로 이루어져 있는지 확인하기 위해, 0번째 행과 0번째 열을 시작점으로 하는 대각선을 각각 확인한다.

근데 이렇게 하니 루프를 2번 돌게 되어서 더 좋은 방법이 있겠다는 생각이 본능적으로 들었다.

코드

function isToeplitzMatrix(matrix: number[][]): boolean {
  // 더 좋은 방법이 있을 것 같다...
  const m = matrix.length;
  const n = matrix[0].length;
  // 0번째 행을 시작점으로 하는 대각선 확인하기
  for (let col = 0; col < n; col++) {
    let y = 1;
    let x = col + 1;
    while (y < m && x < n) {
      if (matrix[y - 1][x - 1] !== matrix[y][x]) return false;
      y++;
      x++;
    }
  }

  // 0번째 행을 시작점으로 하는 대각선 확인하기
  for (let row = 1; row < m; row++) {
    let y = row + 1;
    let x = 1;
    while (y < m && x < n) {
      if (matrix[y - 1][x - 1] !== matrix[y][x]) return false;
      y++;
      x++;
    }
  }

  return true;
}

시간 / 공간 복잡도

• 시간 복잡도: O(M * N) — 행렬의 모든 원소를 순회
• 공간 복잡도: O(1)

풀이 2

아이디어

역시 더 간결한 방법이 있었다. 대각선이 모두 같은 원소인지를 확인하기 위해서 굳이 대각선 단위로 모두 비교할 필요는 없었다. 각 원소들이 자신의 오른쪽 아래 원소와 동일한지를 확인해주면 한번의 루프로도 충분히 검증이 가능하다. 루프를 두번 도는 것보다 가독성 측면에서도 좀 더 이해하기 쉬운 것 같다.

코드

function isToeplitzMatrix(matrix: number[][]): boolean {
  const m = matrix.length;
  const n = matrix[0].length;

  // 각 원소를 오른쪽 아래의 이웃과만 비교한다.
  for (let i = 0; i < m - 1; i++) {
    for (let j = 0; j < n - 1; j++) {
      if (matrix[i][j] !== matrix[i + 1][j + 1]) return false;
    }
  }

  return true;
}

시간 / 공간 복잡도

• 시간 복잡도: O(M * N) — 행렬의 모든 원소를 순회
• 공간 복잡도: O(1)