[알고리즘/Python] LeetCode 74. Search a 2D Matrix

📑 1. 문제 이해

https://leetcode.com/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-interview-150 

Search a 2D Matrix - LeetCode

이 문제는 m * n의 2차원 배열에 대하여 target과 일치하는 원소가 있는지 판별하는 문제입니다. 이때 2차원 배열내 각 배열은 오름차순으로 정렬되어 있으며, n +1 번째 행은 n번째 행의 모든 원소보다 큽니다. 배열의 원소는 음수일 수 있으며 중복이 있을 수 있습니다. m과 n은 최소 1일 수 있습니다. 

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같습니다.

 

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

    - target이 배열 내 존재하는 경우

2. Example2: matrix = [[1,3,5,7], [10,11,16,20], [23,30,34,60]] target = 13

    - target이 배열 내 존재하지 않는 경우

 

더 생각해볼 테스트 케이스는 다음과 같습니다.

 

3. matrix = [[1]] target = 2

    - 1*1배열의 경우

4. matrix = [[-100, -98, -2], [-1, 0, 12]]  target = -101

    - 음수인 원소가 존재하며 target이 모든 원소보다 작은 경우

💡 2. 알고리즘 설계

정렬된 배열에서 특정 원소를 찾아야하는 문제로 이진 검색을 떠올릴 수 있습니다. 원소의 개수가 최대 10,000개로 선형탐색을 해도 되지만 정렬된 배열이라면 이진 탐색을 통해 알고리즘의 효율성을 높일 수 있습니다. 

 이때 문제의 조건에 의하여, matrix[r]의 원소 e에 대하여 matrix[r-1][-1] < e <= matrix[r][-1]이 성립합니다. 이를 활용해 탐색할 row를 하나로 줄일 수 있습니다.

 

1. row를 의미하는 변수 r을 0으로 초기화합니다.

2. target과 행의 마지막 열 원소(row에서 가장 큰 원소)를 비교하여 target이 들어있을 가능성이 있는 행을 선정합니다. 행의 모든 원소는 행의 마지막 열 원소보다 작거나 같고, 이전 행의 마지막 열 원소보다 큽니다. 

3. 만약 r이 len(matrix)와 같다면 target이 모든 원소보다 크다는 의미로 False를 반환합니다.

4. r행을 기준으로 이진탐색을 통해 target이 존재하는지 확인합니다.

def solution(matrix: List[List[int]], target: int) -> bool:
    r = 0
    while r < len(matrix) and matrix[r][-1] < target:
        r += 1
    if r == len(matrix):
        return False

    start = 0
    end = len(matrix[r])

    while start <= end:
        mid = (start + end) // 2
        if matrix[r][mid] == target:
            return True
        elif matrix[r][mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return False

시간 복잡도 및 공간 복잡도

시간 복잡도: O(M + LogN). 이진 탐색을 할 행을 선정하기 위해 최대 M번 포인터를 이동시킵니다. 이후 행에 대해여 이진탐색을 통해 target을 찾기 위해 최대 LogN번 탐색을 진행합니다.

공간 복잡도: O(1)

 

⚒️ 3. 최적화

 이진 탐색의 대상이 되는 행을 선정할때에도 이진 탐색을 통해 탐색 효율성을 높일 수 있습니다. 마지막 열의 원소들도 오름차순으로 정렬된 상태입니다. 마지막 열을 대상으로 이진 탐색을 진행하여 target보다 크거나 같은 원소들 중 가장 인덱스가 작은 행을 선택합니다.

def solution2(matrix: List[List[int]], target: int) -> bool:
    low_r = 0
    hi_r = len(matrix) - 1

    r = None
    while low_r <= hi_r:
        mid = (low_r + hi_r) // 2
        if matrix[mid][-1] >= target:
            r = mid
            hi_r = mid - 1
        else:
            low_r = mid + 1

    if r is None:
        return False

    low_c = 0
    hi_c = len(matrix[r]) - 1

    while low_c <= hi_c:
        mid = (low_c + hi_c) // 2
        if matrix[r][mid] == target:
            return True
        elif matrix[r][mid] < target:
            low_c = mid + 1
        else:
            hi_c = mid - 1

    return False

시간 복잡도 및 공간 복잡도

시간 복잡도: O(Log(M * N)). 마지막 열을 대상으로 이진 탐색하는데 O(LogM), 특정된 행을 대상으로 이진 탐색을 하는데 O(LogN) 복잡도가 되어 총 O(LogN+M) = O(LogN*M)) 복잡도를 가집니다. 선형탐색 후 이진탐색을 한 첫번째 풀이와 비교했을때 실행시간이 73 ms-> 48ms로 빨라짐을 확인할 수 있습니다.

공간 복잡도: O(1)

 ⎌ 4. 검토

테스트 케이스에 대해서 실행 결과를 살펴보면 다음과 같습니다.

 

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

    - 1번행에 대해서 이진 탐색 후 3 찾을 수 있음.

 

2. Example2: matrix = [[1,3,5,7], [10,11,16,20], [23,30,34,60]] target = 13

    - 2번 행에서 이진 탐색 후 값이 반환되지 않고 while문을 빠져나와 False가 반환됨.

 

3. matrix = [[1]] target = 2

    - 모든 원소보다 target이 커서 r 은 None이 되어 이진 탐색을 진행하지 않고 False가 반환됨.

 

4. matrix = [[-100, -98, -2], [-1, 0, 12]]  target = -101

    - 1번 행을 대상으로 이진탐색 후 값이 반환되지 않고 while문을 빠져나와 False가 반환됨.

 

✅ 정리

◎ 2차원 배열에 대해서도 이진 탐색을 통해 효율적으로 탐색할 수 있습니다.