JavaScript로 토플리츠 행렬(Toeplitz Matrix) 여부 확인하기

문제 소개

2차원 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 왼쪽 위에서 오른쪽 아래로 이어지는 모든 대각선의 요소가 서로 동일한지 검사해야 하며, 모든 대각선의 요소가 같다면 true, 하나라도 다르면 false를 반환하면 됩니다.

참고로 이처럼 모든 대각선 요소가 동일한 성질을 가진 행렬을 토플리츠 행렬(Toeplitz Matrix)이라고 부릅니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const arr = [
    [6, 7, 8, 9],
    [2, 6, 7, 8],
    [1, 2, 6, 7],
];

출력

const output = true;

출력 설명

위 배열에서 왼쪽 위 → 오른쪽 아래 방향의 대각선은 다음과 같습니다.

[1], [2,2], [6,6,6], [7,7,7], [8,8], [9]

각 대각선을 구성하는 모든 요소가 동일하므로 결과는 true입니다.

구현 예제

다음은 위 문제를 해결하는 전체 코드입니다.

const arr = [
    [6, 7, 8, 9],
    [2, 6, 7, 8],
    [1, 2, 6, 7],
];
const checkMatrix = (arr = []) => {
    const validate = (row, col) => {
        while (
            row < arr.length
            && col < arr[0].length
            && arr[row + 1]
            && arr[row + 1][col + 1] !== undefined
        ) {
            if (arr[row + 1][col + 1] !== arr[row][col]) {
                return false
            }
            row += 1
            col += 1
        }
        return true
    }
    for (let i = 0; i < arr[0].length; i++) {
        if (!validate(0, i)) {
            return false
        }
    }
    for (let i = 0; i < arr.length; i++) {
        if (!validate(i, 0)) {
            return false
        }
    }
    return true
}
console.log(checkMatrix(arr));

실행 결과

true

코드 동작 원리

핵심 로직은 validate 헬퍼 함수에 있습니다. 이 함수는 시작 좌표 (row, col)를 받아 해당 위치에서 오른쪽 아래 방향으로 한 칸씩 이동하면서 현재 요소와 다음 요소를 비교합니다. 비교 중 값이 다르면 즉시 false를 반환하고, 끝까지 탐색했다면 true를 반환합니다.

그다음 첫 번째 행의 모든 열(validate(0, i))과 첫 번째 열의 모든 행(validate(i, 0))을 각각 시작점으로 순회합니다. 행렬의 모든 대각선은 반드시 첫 번째 행 또는 첫 번째 열에서 시작하기 때문에, 이 두 반복문만으로 전체 대각선을 빠짐없이 검사할 수 있습니다.

이 알고리즘의 시간 복잡도는 O(M × N)(M은 행의 개수, N은 열의 개수)이며, 각 요소를 최대 한 번씩만 방문하므로 매우 효율적입니다.