[파이썬 알고리즘 인터뷰][이진검색] 2D 행렬 검색2

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

row / column 순서로 정렬된 2D 행렬에서 target 찾기

 

책에서 구현된 코드

# 첫 행의 맨 뒤에서 탐색
class Solution:
    def searchMatrix(self, matrix, target):
        # 예외 처리
        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

# 파이썬다운 방식
class Solution:
    def searchMatrix(self, matrix, target):
        return any(target in row for row in matrix)

 

기억해야할 기법

• 첫 행 끝에서부터 탐색하면 될 줄 몰랐다
  • 수의 범위를 생각해내지 못했다
• 파이썬다운 방식은 더 충격적이도록 간단하다
• any
  • OR와 비슷하며, True가 포함되어 있으면 True
    - [True, False, False] -> True
• all
  • AND와 비슷하며, 모두 True면 True
    - [True, True, False] -> False
• 이 책은 이런게 있었으면 좋겠다 생각할 때 그 내용이 포함되어서 좋다

 

내가 구현한 코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        R, C = len(matrix), len(matrix[0])
        r = 0
        hi = C

        while r < R and matrix[r][0] <= target:
            i = bisect.bisect_left(matrix[r], target, 0, hi)
            if i < C and matrix[r][i] == target:
                return True
            hi = i
            r += 1
        return False

• 내가 구현한 코드를 한 줄로 구현할 수 있다
  • 심지어 속도도 더 빠르다
  • 일단 문제를 푸는게 먼저이기 때문에, 방법을 안다면 쉽게라도 풀어내야한다
• 로직을 구상할 때 O(n log n)의 방식이 떠오르면 웬만하면 동작하는 것 같다