[LeetCode] 74. Search a 2D Matrix

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

Algorithm

binary Search를 이용해 푸는 문제이다. 개인적으로 binarySearch를 연습할 수 있는 좋은 문제였다.

python과 java의 각 모듈의 차이가 헷갈려 정리해보았다..

 

Python

python은 bisect 모듈이 있다. 여기서 만약 값이 없으면 아래처럼 해당 값이 들어갈 인덱스를 반환한다. ([]처럼 비었으면 target값이들어갈인덱스 0을 리턴한다.)

nums = [1, 3, 5, 7]
target = 8
place = bisect_left(nums, target)
print(place)  # Output: 4

그래서 나는 특정 값을 찾고 없을땐 -1을 리턴해야 할 땐 아래처럼 이용했다.

from bisect import bisect_left

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        place = bisect_left(nums, target)
        return place if 0 <= place < len(nums) and nums[place]==target else -1

 

Java

자바에는 Arrays.binarySearch() 메서드  가 있다. 이 메서드는 파이썬과 사용법이 다르다. 만약 값이있으면 해당인덱스를 반환하고, 값이 없으면 맨앞의 인덱스를 1부터 세서 음수값으로 반환한다. 그래서 삽입될 인덱스를 구하려면 -(index + 1) 을 하면 된다.

아래 예시를 보자.

int[] arr = {1, 3, 5, 7};
int target = 4;
int index = Arrays.binarySearch(arr, target);

if (index >= 0) {
    System.out.println("4가 들어갈 인덱스: " + index);
} else {
    // Arrays.binarySearch() 메서드는 값이 존재하지 않을 경우 음수 값을 반환
    // 음수 값의 절댓값은 삽입 위치
    System.out.println("4 insertionIndex: " + index);
    int insertionIndex = -(index + 1);
    System.out.println("4는 배열에 존재하지 않습니다. 삽입 위치: " + insertionIndex);
}

//4 insertionIndex: -3
//4는 배열에 존재하지 않습니다. 삽입 위치: 2

 

여기서 중요한것은 시간복잡도인데, O(m*n)이면 안되기때문에 브루트포스를 하면안되고, 그래서 정렬되었다는 특징을 이용해 이진탐색을 진행했다. 시간복잡도는 따라서 O(logm+logn)으로 풀 수 있었다.

내가 푼 방식은 다음과 같다.

먼저 각 행의 첫 요소들을 대상으로 binarySearch를 진행해, target 위치 행을 찾는다.

그리고 타겟값이 첫요소중에 있으면 리턴한다.

만약 첫요소중에 없다면 타겟행인덱스-=1 을해주고(삽입위치가아닌 포함위치행), 이때 타겟행인덱스가 범위를 벗어났다면 False를 리턴한다.

그리고 찾은 타겟행에서 다시 이진탐색을 진행해 답을 리턴한다.

---

Java

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 각 행의 첫 번째 요소들
        int[] eachRowFirst = new int[m];
        for (int i = 0; i < m; i++) {
            eachRowFirst[i] = matrix[i][0];
        }

        // target이 위치할 행을 찾기
        int targetRow = Arrays.binarySearch(eachRowFirst, target);
        
        // 만약 행 첫번째위치에 답이 있다면
        if (0 <= targetRow && targetRow < m && matrix[targetRow][0] == target) {
            return true;
        }

        if (targetRow < 0) { // 답이 없다면 음수 반환
            System.out.println(targetRow);
            targetRow = -(targetRow + 1) - 1; //쉽게생각..삽입위치인덱스-1==해당위치
            System.out.println(targetRow);
        }


        // 찾은 행이 행렬 범위를 벗어날 경우, False
        if (targetRow < 0 || m <= targetRow) {
            return false;
        }

        // 찾은 행에서 target을 이진 탐색
        int ans = Arrays.binarySearch(matrix[targetRow], target);
        return 0 <= ans && ans < n && matrix[targetRow][ans] == target;
    }
}

Python

from bisect import bisect_left

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        
        # 각 행의 첫 번째 요소들
        eachrow_first = [row[0] for row in matrix]
        
        # target이 위치할 행을 찾기
        target_row = bisect_left(eachrow_first, target)

        # 만약 행 첫번째위치에 답이 있다면
        if 0<=target_row<m and matrix[target_row][0] == target:
            return True
        else:
            # 찾은 행이 행렬 범위를 벗어날 경우, False
            target_row-=1 # 행인덱스
            if target_row<0 or m<=target_row:
                return False
            
            # 찾은 행에서 target을 이진 탐색
            ans = bisect_left(matrix[target_row], target)
            
            return 0 <= ans < n and matrix[target_row][ans] == target