이진검색

들어가기 전에

1. bisect.bisect_left 는 대표적인 이진검색 함수이다.
2. 만약 위의 함수를 사용할 수 없는 상황이면 left, right 포인터와 반복문을 사용해보자.

Question 69: 2D 행렬의 검색2

$m \times n$ 행렬에서 값을 찾아내는 효율적인 알고리즘을 구현하라. 행렬은 왼쪽에서 오른쪽, 위에서 아래로 오름차순으로 정렬되어 있다.

입력: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

출력: True

---

내 풀이

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for lst in matrix:
            index = bisect.bisect_left(lst, target)
            if len(lst) > 0 and len(lst) > index and lst[index] == target:
                return True
        return False

결과

Runtime: 172 ms, faster than 90.95% of Python3 online submissions for Search a 2D Matrix II. Memory Usage: 20.5 MB, less than 43.81% of Python3 online submissions for Search a 2D Matrix II.

중요 내용

1. bisect_left(nums, target)는 정렬된 순서를 유지하도록 nums에 target을 삽입할 위치를 찾는다. 만약 target 값이 nums 안에 있을 경우 그 값의 인덱스를 리턴한다.

---

풀이 1: 첫 행의 맨 뒤에서 검색

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        
        row = 0
        col = len(matrix[0])-1
        
        while row <= len(matrix) - 1 and col >= 0:
            if target == matrix[row][col]:
                return True
            
            elif target < matrix[row][col]:
                col -= 1
            
            elif target > matrix[row][col]:
                row += 1
        
        return False

중요 내용

1. row와 col의 초기 값을 다음과 같이 설정해도 코드가 정상적으로 실행된다.

        row = len(matrix) - 1
        col = 0
        
        while row >= 0 and col <= len(matrix[0]) - 1:
            
            if target == matrix[row][col]:
                return True
            
            elif target > matrix[row][col]:
                col += 1
            
            elif target < matrix[row][col]:
                row -= 1

풀이 2: 파이썬다운 방식

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        return any(target in row for row in matrix)

중요 내용

1. any() 함수는 포함된 값 중 어느 하나가 참이라면 항상 참으로 출력한다. 논리 연산의 OR과 비슷하다.
2. all() 함수는 모든 값이 참이어야 참을 리턴한다. 논리 연산의 AND와 비슷하다.