[LeetCode] 74. Search a 2D Matrix - 이분탐색(BinarySearch) JAVA

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

코드설명

이분탐색(BinarySearch)을 활용합니다.

 

2D Matrix를 사실상 1D Matrix로 수정해서 풉니다.

이떄 유의점은, matrix 길이가 1일때를 대비하기 위해 아래와 같이 BinarySearch에서 먼저 처리하고 진행합니다.

if(matrix[left/m][left%m] == target) return left;
if(matrix[right/m][right%m] == target) return right;

 

처음에 접근한 비효율적인 방법입니다. (시간복잡도는 O(logM*N) 내에 동작하긴 합니다만, 코드가 길고, 상대적으로 느립니다.)

먼저, row에서 몇번쨰 row에 존재하는지 확인하기 위해 RowBinarySearch를 실행합니다.

이떄, 중요한점은 LowerBound로 처리했으므로, target값보다 더 큰값이 반환될 수 있습니다. 이는, 현재 Matrix[targetRow][0]값과 target값과 같다면 그대로 두고, target 값과 다르다면 -1 처리합니다.

해당 Row값을 가지고서 Matrix[targetRow][Col] 값에 대해서도 똑같이 ColBinarySearch를 실행하여 인덱스 값을 가져오면 됩니다

문제에서 틀릴 수 있는 점은 Edge Case들입니다. 만약 matrix.length == 1 인경우, target이 없어서 범위를 벗어나는 경우 등등 각각 처리를 Edge Case로 처리하느라 main함수의 코드가 많이 복잡합니다. (코드를 잘못짰다는 의미입니다..)

코드

처음에 작성한 코드입니다.

물론, O(log (m * n) )의 시간복잡도를 가지지만, 코드가 상당히 깁니다.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 1){
            int targetCol = ColBS(matrix, 0, target, 0, matrix[0].length - 1);
            if(targetCol < 0 || targetCol >= matrix[0].length) return false;
            return matrix[0][targetCol] == target;
        }
        int targetRow = RowBS(matrix, target, 0, matrix.length - 1);
        if(targetRow > 0 && targetRow < matrix.length && matrix[targetRow][0] > target){
            targetRow = targetRow - 1;
        }
        if(targetRow >= matrix.length){
            targetRow -= 1;
        }
        if(targetRow < 0 || targetRow >= matrix.length) return false;
        int targetCol = ColBS(matrix, targetRow, target, 0, matrix[0].length - 1);
        if(targetCol < 0 || targetCol >= matrix[0].length) return false;
        return matrix[targetRow][targetCol] == target;
    }

    int RowBS(int[][] matrix, int target, int start, int end){
        int left = start - 1;
        int right =end + 1;
        while(left +1 < right){
            int mid = (left + right) / 2;

            if(matrix[mid][0] < target){
                left = mid;
            } else if(matrix[mid][0] >= target){
                right = mid;
            }
        }
        return right;
    }
    int ColBS(int[][] matrix, int row, int target, int start, int end){
        int left = start - 1;
        int right =end + 1;
        while(left +1 < right){
            int mid = (left + right) / 2;
            if(matrix[row][mid] < target){
                left = mid;
            } else if(matrix[row][mid] >= target){
                right = mid;
            }
        }
        return right;
    }

}

 

정답코드2입니다.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int answer = bs(matrix, target, matrix.length, matrix[0].length, 0, matrix.length * matrix[0].length - 1);
        return target == matrix[answer / matrix[0].length][answer % matrix[0].length];
    }

    int bs(int[][] matrix, int target, int n, int m, int start, int end){
        int left = start;
        int right = end;
        if(matrix[left/m][left%m] == target) return left;
        if(matrix[right/m][right%m] == target) return right;
        while(left + 1 < right){
            int mid = (left + right) / 2;
            int nRow = mid / m;
            int nCol = mid % m;
            if(matrix[nRow][nCol] < target){
                left = mid;
            }else if(matrix[nRow][nCol] >= target){
                right = mid;
            }
        }
        return right;
    }
}