[LeetCode] 74. Search a 2D Matrix

Search a 2D Matrix - LeetCode

int형 2차원 배열과 target 숫자가 주어지면 2차원 배열안에 target이 있는지 찾아 true or false를 반환하는 문제입니다.

O(log(n*m))의 시간복잡도안에 구현해야 합니다.

 

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

 

 

문제 접근

log(n)안에 해결하라는 조건을보고 이분탐색을 사용해야겠다고 생각했습니다.

2차원 배열을 이분탐색하여 해결하였습니다.

 

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int mid = -1;
        for (int i = 0; i < row; i++) {
            int l = 0;
            int r = matrix[0].length - 1;
            while (l <= r) {
                mid = (l + r) / 2;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] > target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return false;
    }

시간복잡도

for문 안에서 이분탐색을 사용하고 있습니다.

시간복잡도는 O(log(n*m))입니다.

 

다른사람의 풀이

같은 이분탐색을 사용하지만, while문의 조건을 잘 설정하여 가독성 좋은 코드를 작성하였습니다.

 

또한 row에 대한 값을 for문으로 탐색을 한 제 코드와는 달리

row를 변수로 설정하여 while문안에서 ++을 해주어 row를 변경하였습니다. 

 

target보다 row의 마지막값이  작을경우 row++을 하여 불필요한 row를 탐색하지 않게 하였습니다.

public boolean searchMatrix(int[][] matrix, int target) {
        
        int row = 0;
        int col = 0;
        
        while(row < matrix.length && col < matrix[0].length) {
            if(matrix[row][col] == target) {
                return true;
            }
            else if(matrix[row][matrix[0].length - 1] < target) {
                row++;
            }
            else col++;
        }
        return false;
    }

 

시간복잡도

시간복잡도는 O(log(n*m))입니다.

 

 

느낀점

다시한번 느끼지만, while문의 조건을 잘 설정하는것은 코드의 가독성을 높이는 중요한 요인입니다.

어떤 조건이 들어가야할지 깊이 생각해 볼 필요가 있습니다.

 

참고

LeetCode 74(Search a 2D Matrix, java)