Search a 2D Matrix II | LeetCode 806 | Python3 🐍

 

📄 목차

 

 

🤔 문제 : Search a 2D Matrix II | LeetCode 806

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/806/

Matirx상에서 타겟값이 있는지 확인하는 문제입니다.

단, Matrix는 각 행, 열이 모두 정렬되어있습니다. 

💡 풀이

1. 각 열에 대해 BS

당연히 BS로 접근해야 하는 문제로 생각했습니다.

1) 각 열의 첫번째 항을 순회합니다. 첫 행을 순회하는게 되겠죠.

2) 열의 첫번재 값이 타겟값보다 작으면, 그 열에 타겟값이 있을 수 있다는 뜻이겠죠? 해당 열에 대해 BS를 합니다.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def bs(listIdx, st, ed):
            if st > ed: return False
            md = int((st + ed) /2)
            if matrix[listIdx][md] == target: return True
            if matrix[listIdx][md] < target: return bs(listIdx, md+1, ed)
            return bs(listIdx, st, md-1)

        for listIdx in range(len(matrix)): # 각 열에 대해서 
            if matrix[listIdx][0] == target: return True
            if matrix[listIdx][0] < target: # 첫번째 값이 타겟값보다 작으면 BS
                if bs(listIdx, 0, len(matrix[listIdx])-1):
                    return True
        return False

 

Time Complexity
최악의 경우 마지막 열에 타겟값이 있으면 logN을 n번 수행합니다.
O(NlogN)

 

 

2. BS를 쓰지 않는 풀이?!

1번풀이가 좀.. 막무가내인가(?) 하는 생각이 들어 다른 풀이들을 찾아봤는데 역시나 획기적인 풀이가 있었습니다.

 

왼쪽맨 아래 값 부터 타겟값을 찾아가는방식입니다.

현재 보고있는 값이 타겟값보다 크다면?

지금보다 오른쪽 아래에는 타겟값이 있을 수 없겠죠. 현재값의 오른쪽 아래쪽은 다 현재값보다 크니깐요.

그럼 보고 있는 값을 위로 한 칸  옮깁니다. 

 

현재 보고있는 값이 타겟값보다 작다면?

지금보다 왼쪽 위에는 타겟값이 있을 수 없겠죠. 현재값의 왼쪽 위는 다 현재값보다 크니깐요.

그럼 보고 있는 값을 오른쪽으로 한 칸  옮깁니다. 

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        
        def solve(i, j):
            if i < 0: return False
            if j >= n: return False
            
            if matrix[i][j] == target: return True
            if matrix[i][j] < target: return solve(i, j+1)
            if matrix[i][j] > target: return solve(i-1, j)          
        return solve(m-1, 0)

 

Time complexity
타겟값이 행렬의 가장 오른쪽 가장 위에 있는 경우가 최악의 경우가 되고
이 때의 time complexity는 m:가로길이, n:세로길이라 할 때
O(m+n)