[NeetCode-LeetCode] Search a 2D Matrix JAVA

반응형

728x90

[NeetCode-LeetCode] Search a 2D Matrix - Medium 

---

접근

• 이진 탐색

---

풀이

오름차순으로 정렬된 2차원 배열에서 target 값이 존재하는지 찾는 문제이다. O(log(m * n))의 시간 복잡도로 해결을 하라고 되어 있는 이진 탐색 카테고리의 문제이다. 2차원 배열에서 이진 탐색을 사용하기 위해 2차원 좌표를 그대로 사용해 한 번 풀어보려 했으나 범위 조정이 매끄럽게 되지 않고 효율적이지 못해 그만뒀다.

    public boolean searchMatrix(int[][] matrix, int target) {
        int start = 0;
        int end = matrix.length * matrix[0].length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            int value = matrix[mid / matrix[0].length][mid % matrix[0].length];

            if (value == target) {
                return true;
            } else if (value < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return false;
    }

2차원 좌표를 그대로 사용하는 대신 2차원 배열을 1차원 배열로 쭉 나열했다 가정하고 해당 1차원 배열의 위치를 2차원 배열로 변환해 사용하는 것이다. 3 * 4의 배열이라면 1차원 배열로 펼쳤을 때 0~11번 인덱스까지 존재하게 되고 중간 값이 5가 된다면 [1,1] 번지의 값이 되는 것이다. 2차원 좌표에 알맞게 변환시켜 이진 탐색을 수행하면 된다. 

이진탐색

다른 코드들은 어떻게 풀어졌나 0ms의 코드를 봤는데

??????

문제에선 O(log(m * n))으로 풀기를 요구하면서 테스트케이스는 O(n * m)으로 풀어도 0ms 가 나오게 주어진다는 게 아이러니하다...

---

전체 코드

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int start = 0;
        int end = matrix.length * matrix[0].length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            int value = matrix[mid / matrix[0].length][mid % matrix[0].length];

            if (value == target) {
                return true;
            } else if (value < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return false;
    }
}