[LeetCode#74] Search a 2D Matrix

 

❒ Description

---

날짜	2024.10.02 (수)
레벨	Medium
제목	Search a 2D Matrix
링크	https://leetcode.com/problems/search-a-2d-matrix/description/
알고리즘	Binary Search
시간 복잡도	O(log(n+m))

 

 

 

 

 

❒ Ideation

---

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

matrix 내의 subArray를 그냥 하나의 덩어리로 바라본다. 우선 matrix에 대해서 binary search를

진행하고, target이 포함된 subArray를 찾는다. 만약 없다면 null을 반환한다.

• subArray[firstIdx] > target : right cursor 이동
• subArray[lastIdx] < target : left cursor 이동
• subArray[firstIdx] <=  target <=subArray[lastIdx] : 정답!

그리고 위 과정에서 얻은 array[10, 11, 16, 20]를 또 binary search한다.

 

 

 

 

 

❒ Solution

---

1. 2번의 Binary search

public class V1 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] searchedArr = binarySearchForMatrix(matrix, target);
        if (searchedArr == null) return null;
        return binarySearch(searchedArr, target);
        
        // 직관성 Bad
        // return searchedArr != null && binarySearch(searchedArr, target);
    }

    private int[] binarySearchForMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = matrix.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int[] subArr = matrix[mid];
            if (subArr[0] > target) {
                right = mid - 1;
            } else if (subArr[subArr.length - 1] < target) {
                left = mid + 1;
            } else {
                return subArr;
            }
        }
        return null;
    }

    private boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

 

 

2. row와 col으로 바라보는 관점

public class V2 {
    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) {
                col --;
            } else if (matrix[row][col] < target) {
                row ++;
            } else {
                return false;
            }
        }
        return true;
    }
}

여기서는 현재 위치가 row와 col 이내에 있는지를 판단해야 한다. 처음에는 row를 0, col을 마지막으로 정한다.

• target이 현재 row에 없다면 ? 다음 row로 이동
• target이 현재 col에 없다면 ? 이전 row로 이동

 

 

3. Matrix를 하나의 정렬된 배열로 바라보는 관점

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0, right = m * n - 1;
            
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 핵심 로직
        int midVal = matrix[mid / n][mid % n] 
        if (midVal < target) {
            left = mid + 1;
        } else if (midVal > target) {
            right = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

이 풀이는 주어진 matrix를 하나의 정렬된 배열로 바라보는 것이다. 

 

int midVal = matrix[mid / n][mid % n]

이 로직이 가장 핵심인데,

mid를 열의 개수 n으로 나누면, 2차원 행렬에서의 행(row) 인덱스를 구할 수 있다.

그리고 mid를 n으로 나눈 나머지 값이 해당 행에서의 열(column) 인덱스가 된다.

크기가 6인 원형 큐에서 마지막 인덱스 5에 위치한 값이 한 칸 앞으로 가면 idx = 6가 되어야 하지만
최대 idx는 5 이므로, 다음 인덱스는 `6 % 큐의 크기(6) = 0` 로 계산하는 거랑 비슷한 맥락인듯

 

 

 

 

 

---