LeetCode: 74번 (Search a 2D Matrix) [JAVA]

문제 링크

https://leetcode.com/problems/search-a-2d-matrix/

Search a 2D Matrix - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 숫자 target이 이차원 배열에 숫자들보다 아예 작거나 크다면 false 반환
2. 우선 행 단위로 해당 숫자가 존재할 행을 이진 탐색
3. 이후 열 단위로 해당 숫자가 존재할 열을 이진 탐색
   1) 이 과정에서 해당 숫자가 존재하면 true 반환
4. 숫자가 존재하지 않는다면 false 반환

 문제 자체는 그리 어렵지 않다. 순차적으로 정렬되어 채워져있는 이차원 배열에서, 주어진 숫자 target에 맞는 숫자가 기존에 존재한다면 true를, 아니라면 false를 반환하면 된다.
 애초에 이차원 배열의 숫자들이 정렬되어 주어지기 때문에, 이중 for문으로 순차대로 숫자를 찾아가다 답을 반환해도 되지만 좀 더 효율성을 위해선 이진탐색을 활용할 수 있다. 우선적으로 행 단위로 이진 탐색을 진행해 해당 숫자가 존재할 행을 찾고, 이후 그 행에서 다시 이진 탐색을 진행해 해당 숫자가 존재할 열을 탐색해 나가면 된다.
 그러한 과정에서 해당 숫자가 존재한다면 true를, 존재하지 않는다면 false를 반환해주면 된다.

 

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;

        if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) {//너무 크거나 작다면
            return false;
        }

        int startRow = 0, endRow = m - 1;

        while (startRow <= endRow) {//해당 숫자가 존재할 행을 이진탐색
            int midRow = (startRow + endRow) / 2;

            if (matrix[midRow][0] < target) {
                startRow = midRow + 1;
            } else if (matrix[midRow][0] == target) {
                return true;
            } else {
                endRow = midRow - 1;
            }
        }

        int startCol = 0, endCol = n - 1;

        while (startCol <= endCol) {//해당 숫자가 존재할 열을 이진탐색
            int midCol = (startCol + endCol) / 2;

            if (matrix[endRow][midCol] < target) {
                startCol = midCol + 1;
            } else if (matrix[endRow][midCol] == target) {
                return true;
            } else {
                endCol = midCol - 1;
            }
        }

        return false;
    }
}

결과