[Java] 74. Search a 2D Matrix

문제 파악

m x n 행렬이 주어진다.

 

각 행은 비내림차순으로 정렬되어있다.

 

각 행의 첫 원소는 이전 행의 마지막 원소보다 크다.

 

target이 행렬에 존재하는지 찾아야한다.

 

시간 복잡도는 O(log(m*n)) 으로 수행해야한다.

 

---

풀이

 

1️⃣ 이분 탐색

💡 떠오른 Idea

행렬 내에 원소가 존재하는지만 판단하면 되기 때문에, 2차원 행렬을 1차원으로 변환시킨 후 이분탐색을 진행하면

시간복잡도 O(log(m*n)) 도 만족하면서, 문제를 해결할 수 있을 것이라 생각이 들었다.

또한, 각 행 내 원소와 행들 끼리 정렬되어 있어서 편하게 이분탐색을 사용할 수 있을 것이라고 판단하였다.

위 아이디어를 바탕으로, 특정 원소를 찾아내는 이분탐색 코드를 구현하였다.

 

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] merged = new int[matrix.length * matrix[0].length];
        int idx = 0;
        for (int[] row : matrix) {
            for (int element : row) {
                merged[idx++] = element;
            }
        }
        return bs(merged, target);
    }

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

 

결과

 

2️⃣ Arrays.binarySearch() 사용

이분 탐색 구현 코드가 정 생각나지 않을 때, 사용할 수 있는 방법이다.

 

코드는 간결해지지만, 이분탐색을 직접 구현하라고 했을 때 당황할 수 있으니 웬만하면 직접 구현하고

 

만약, 코테 이외에 이분탐색을 사용하게 될때에는 만들어진 메서드를 사용하면 될 것 같다.

 

import java.util.*;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] merged = new int[matrix.length * matrix[0].length];
        int idx = 0;
        for (int[] row : matrix) {
            for (int element : row) {
                merged[idx++] = element;
            }
        }
        return Arrays.binarySearch(merged, target) >= 0 ? true : false;
    }
}

 

결과

결과를 비교해보면, 직접 구현한 이분탐색보다 메모리를 약간 더 사용한 것으로 보인다.

 

---

📖 회고

 

이분 탐색을 통해 특정 원소를 검색하거나, 삽입할 수 있는 위치를 찾아보는 문제들을 풀어보면서 다양한 문제에서 활용할 수 있는 방법을 터득하게 된 것 같다.

 

LeetCode 외에도 응용 문제들을 여러개 풀어봐야겠다는 생각이 들었다.