Search a 2D Matrix II - LeetCode

문제 접근 🤔

• 이진 탐색(이분 탐색)을 통해 매 행마다 target과 같은 값이 있는지 확인하고 존재한다면 True, 존재하지 않으면 False를 반환하면 되는 문제.
• 브루트포스를 이용해서 해결할 수도 있지만 오름차순으로 정렬되어 있는 행렬이기 때문에 빠른 처리를 위해서는 이분 탐색을 고려해보아야 한다.

• 주어진 행렬은 행, 열 모두 오름차순으로 정렬되어 있으므로 0번째 행부터 순서대로 target의 존재를 확인하면 된다.
• 현재 행의 범위 안에 타겟이 속한다면 타겟이 존재할 수도 있으므로 이분 탐색을 진행하면 된다.
• low, high 의 초기값을 각각 0(첫번째 인덱스), 열의 길이로 선언해준다.
• low가 high보다 커지지 않을 때까지 반복문을 돌며, low와 high의 중앙값인 mid를 통해 타겟의 존재 여부를 확인한다.
• matrix[i][mid]이 타겟과 같다면 True를 반환해준다.
• 타겟보다 작다면 탐색 범위를 (mid + 1, high)로, 크다면 탐색 범위를 (low, mid)로 좁혀준다.
• 이 과정을 통해 모든 행을 확인해보았을 때도 같은 값을 찾지 못했다면 False를 반환한다.
• 행의 개수를 M 열의 개수를 N 이라고 했을 때, 이분 탐색을 이용한 이 문제의 총 시간 복잡도는 O(M log N) 을 갖는다.
  
  
  

놓쳤던 부분 😅

• 이진 탐색에서는 없음.
• 이진 탐색 전에 먼저 떠오른 풀이가 있어 제출 해보았는데, 파이썬에선 통과가 되었고 JS에서는 시간초과가 났다 🤯
• 혹시 JS에서 배열에 같은 원소가 있는지 확인하는 includes 함수에서 오래 걸리나? 해서
• 시간 복잡도가 O(N)인 includes 함수에서 O(1)의 시간 복잡도를 갖는 Set의 has 함수로 변경하여 확인해보았을 때도 여전히 시간 초과가 났다.
• 파이썬의 in 연산자도 list에서 O(N)의 시간복잡도를 갖는데, 왜 파이썬은 되고 JS는 안 되는거죠? (JS 이지매 당함)
• 심지어 시간 복잡도가 O(logN)인 이진 탐색 풀이보다도 조금 빠른 결과물이 나왔다?!
• 왜 이런 차이가 나는 것인지는 조금 더 찾아봐야 될 듯.
  
  
  

코드 😁

파이썬 코드(142 ms)

# 이진 탐색 풀이 (시간: 142 ms)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row, col = len(matrix), len(matrix[0])
        
        for i in range(row):
            if matrix[i][0] <= target and matrix[i][-1] >= target:
                low, high = 0, col

                while (low < high):
                    mid = (low + high) // 2
                    
                    if matrix[i][mid] == target:
                        return True
                    elif matrix[i][mid] < target:
                        low = mid + 1
                    else:
                        high = mid
                        
        return False

# 행렬의 매 행마다 원하는 값이 있는지 확인하는 풀이 (시간: 137 ms)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            if target in row:
                return True
        return False

자바스크립트 코드(862 ms)

const searchMatrix = (matrix, target) => {
    let [row, col] = [matrix.length, matrix[0].length];

    for (let i = 0; i < row; i++) {
        let [low, high] = [0, col];

        while (low < high) {
            let mid = ~~((low + high) / 2);

            if (matrix[i][mid] === target) {
                return true;
            } else if (matrix[i][mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
    }
    return false;
};