LeetCode

LeetCode 74 Search a 2D Matrix 풀이: 2차원 배열을 평탄화한 이분 탐색

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

각 행이 정렬되어 있을 뿐 아니라 다음 행의 첫 값이 이전 행의 마지막 값보다 크다는 조건이 있다. 행렬 전체를 하나의 정렬 배열처럼 볼 수 있고, 1차원 인덱스를 행과 열로 변환하면 이분 탐색을 그대로 적용할 수 있으므로 Level 2로 판단했다.

1. 문제 요약

m x n 크기의 정수 행렬 matrix와 target이 주어질 때, 행렬 안에 target이 있으면 True, 없으면 False를 반환한다.

행렬은 다음 두 조건을 만족한다.

  • 각 행은 오름차순으로 정렬되어 있다.
  • 다음 행의 첫 번째 값은 이전 행의 마지막 값보다 크다.

이 조건 때문에 행렬을 행 우선 순서로 이어 붙이면 하나의 오름차순 배열과 같은 순서가 된다. 행과 열의 크기는 각각 1 이상 100 이하이고, 목표 시간 복잡도는 O(log(mn))이다.

다음 행렬은 논리적으로 아래와 같은 하나의 배열이다.

matrix = [[1, 3, 5, 7],
          [10, 11, 16, 20],
          [23, 30, 34, 60]]

평탄화한 순서 = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

판정 함수와 탐색 구간

행렬의 전체 원소 수를 total = rows * cols라고 하고, 가상의 1차원 인덱스 구간 [left, right]를 사용한다. 각 반복에서 중간 인덱스 mid의 값을 행렬에서 다음과 같이 가져온다.

row = mid // cols
col = mid % cols
value = matrix[row][col]

이 변환은 행 우선으로 원소를 나열했을 때의 위치와 정확히 대응한다.

  • value == target: 찾았으므로 True를 반환한다.
  • value < target: 현재 값과 왼쪽 후보는 모두 작으므로 left = mid + 1로 갱신한다.
  • value > target: 현재 값과 오른쪽 후보는 모두 크므로 right = mid - 1로 갱신한다.

반복이 끝날 때까지 찾지 못하면 False를 반환한다.

가상 인덱스를 행과 열로 되돌리는 방법

행별 정렬만으로는 행렬 전체를 바로 이분 탐색할 수 없다. 다음 행의 첫 값이 이전 행의 마지막 값보다 작을 수 있다면 행과 행 사이의 전역 순서가 깨진다.

하지만 이 문제에서는 다음 행의 첫 값이 항상 이전 행의 마지막 값보다 크므로, 행렬의 행 우선 순서가 전체적으로 오름차순이다. 실제로 배열을 새로 만들 필요 없이 인덱스 변환만으로 평탄화된 배열을 읽을 수 있다.

상태 전이와 경계 처리

전체 원소 수가 rows * cols이므로 초기 경계는 left = 0, right = rows * cols - 1이다. 닫힌 구간을 사용하기 때문에 현재 mid가 target이 아니라면 다음 경계에서 mid를 반드시 제외해야 한다.

작으면 left = mid + 1
크면 right = mid - 1

mid를 제외하지 않고 left = mid 또는 right = mid로 갱신하면 원소가 두 개 남은 상황에서 경계가 변하지 않아 무한 반복이 발생할 수 있다.

오답 접근과 반례

모든 행을 순서대로 확인하는 선형 탐색은 정답을 구할 수 있지만 목표 복잡도 O(log(mn))를 만족하지 못한다. 100 x 100 행렬에서 target이 마지막에 있거나 없으면 최대 10,000개 원소를 확인해야 한다.

행을 먼저 찾고 행 안에서 다시 이분 탐색하는 방식도 가능하지만, 행 선택과 열 탐색을 각각 구현해야 한다. 이 문제의 전역 정렬 조건을 사용하면 하나의 이분 탐색으로 두 단계를 합칠 수 있다.

시간·공간 복잡도

매 단계에서 후보 원소 수가 절반으로 줄어들므로 시간 복잡도는 O(log(mn))이다. 행렬을 새 배열로 복사하지 않고 중간 인덱스를 행·열로 변환하므로 추가 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

mid를 가상의 1차원 인덱스로 사용하고 divmod(mid, cols)로 행과 열을 한 번에 계산한다. 행렬의 실제 데이터는 변경하지 않는다.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        left = 0
        right = rows * cols - 1

        while left <= right:
            mid = left + (right - left) // 2
            row, col = divmod(mid, cols)
            value = matrix[row][col]

            if value == target:
                return True
            if value < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

divmod(mid, cols)의 몫은 행 번호이고 나머지는 열 번호다. 열의 개수가 4이고 mid = 6이면 row = 1, col = 2가 되어 두 번째 행의 세 번째 원소를 가리킨다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 행렬 검색 성공·실패와 최소 행렬 경계를 확인할 수 있다.

solver = Solution()
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
assert solver.searchMatrix(matrix, 3) is True
assert solver.searchMatrix(matrix, 13) is False
assert solver.searchMatrix([[1]], 1) is True

4. 공식 예제와 추가 검증

작성한 searchMatrix 함수를 Python으로 실행해 공식 예제와 단일 행·단일 원소·음수 경계를 포함한 사례를 확인했다.

공식 예제

입력 기대 출력 확인 결과
matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 True 통과
matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=13 False 통과

추가 검증 1: 한 원소 행렬

입력: matrix = [[1]], target = 1
기대 출력: True
확인 결과: 통과
검증 목적: 시작과 끝 경계가 같은 최소 행렬에서 target을 찾는지 확인

추가 검증 2: 한 원소 행렬에서 target이 없는 경우

입력: matrix = [[1]], target = 2
기대 출력: False
확인 결과: 통과
검증 목적: 단일 후보를 제외한 뒤 False를 반환하는지 확인

추가 검증 3: 행 경계를 넘나드는 target

입력: matrix = [[1,3,5],[7,9,11]], target = 7
기대 출력: True
확인 결과: 통과
검증 목적: 평탄화된 인덱스가 다음 행의 첫 열로 변환되는지 확인

추가 검증 4: 음수와 존재하지 않는 값

입력: matrix = [[-10,-5],[-2,0],[3,8]], target = -2
기대 출력: True
확인 결과: 통과

입력: matrix = [[-10,-5],[-2,0],[3,8]], target = 1
기대 출력: False
확인 결과: 통과
검증 목적: 음수 값과 정렬 순서 사이의 빈 위치를 함께 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

행을 먼저 이분 탐색으로 선택한 뒤 해당 행에서 다시 이분 탐색하는 방식도 O(log m + log n) 시간에 동작한다. 하지만 전역 정렬 조건이 있으므로 전체 원소를 가상의 1차원 배열로 보고 한 번만 탐색하면 구현이 더 단순하고 O(log(mn)) 조건을 직접 만족시킬 수 있다.

행렬을 실제 1차원 배열로 복사하면 인덱스 변환은 필요 없지만 O(mn) 추가 공간이 필요하다. 이 글의 방식은 원본 행렬을 그대로 사용하면서 논리적으로만 평탄화한다.

마무리

Search a 2D Matrix는 행렬을 새 배열로 복사하지 않고도 행 우선 순서가 하나의 오름차순 배열이라는 사실을 이용할 수 있는 문제다. 가상의 1차원 중간 인덱스를 행과 열로 변환해 이분 탐색을 수행하면 O(log(mn)) 시간과 O(1) 공간으로 target의 존재 여부를 판단할 수 있다.

#이분탐색#LeetCode#난이도 2