[LeetCode] 74. Search a 2D Matrix - 문제풀이

Description

행>렬 순서대로 정렬된 2차원 배열(행렬)에서 주어진 target값을 찾는 문제입니다. 값이 없을 경우 false를 반환해주시면 됩니다.

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

Solution 1. 전체 탐색(Brute force)

public boolean searchMatrix(int[][] matrix, int target) {
`
    // 1. brute force  O(N)
    int m = matrix.length;
    int n = matrix[0].length;
    int idx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(matrix[i][j] == target){
                return true;
            }
        }
    }
    return false;
}

2차원 배열을 전체 탐색을 통해 모든 값을 순환하며 target과 일치하는 값을 찾아갑니다.

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(1)

Solution 2. 이진 탐색(Binary Serach)

public boolean searchMatrix(int[][] matrix, int target) {

    // 2. Binary Search O(LogN)
    int m = matrix.length;
    int n = matrix[0].length;
    int start = 0;     // 1차원 배열일때의 index
    int end = m*n-1;  // 1차원 배열일때의 index
    while(start <= end){
        int mid = start + (end-start)/2;
        int r = mid / n;
        int c = mid % n;
        int num = matrix[r][c];
        if(num == target){
            return true;
        }else if(num > target){
            end = mid-1;
        }else{
            start = mid+1;
        }
    }
    return false;
}

정렬되어 있는 1차원 배열과 마찬가지기 때문에 이진 탐색(Binary Serach)로 찾아 시간복잡도를 줄일 수 있습니다. 1차원 배열일 때와 마찬가지로 이진탐색을 하며 1차원 배열의 인덱스(mid)일때 2차원배열의 인덱스만 찾아주는 부분만 추가됩니다.

• 시간 복잡도 : O(LogN)
• 공간 복잡도 : O(1)

Reference

Search a 2D Matrix - LeetCode