[문제풀이] Leetcode 74. Search a 2D Matrix 자바 풀이

👉 문제

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

입출력 예시:

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

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

✨ 풀이

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length-1;
        while(row < matrix.length && col >= 0) {
            if(matrix[row][col]==target) return true;
            if(matrix[row][col] < target) row++;
            else col--;
        } return false;
    }
}

풀이 노트:

• 이진 탐색 응용 문제로, 2차원 배열에서 타겟 넘버를 찾아야 한다.
• 1차원 배열의 경우 start와 end를 기준으로 좁혀나가는데, 2차원 배열이기 때문에 row와 col을 기준으로 좁혀나간다.
• 어떤 기준으로 2개 혹은 3개의 인덱스를 두고, ==target이 될 때까지 인덱스를 늘리거나 줄이는 이진 탐색 알고리즘 방식이 머리에 제법 흡수된 것 같다!