240 Search a 2D Matrix II

• 240 Search a 2D Matrix II
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 코드
      • 1 결과: 성공
    • 2nd 책 풀이
      • 2 코드
      • 2 결과: 성공
    • 3rd 책 풀이
      • 3 코드
      • 3 결과: 성공

240 Search a 2D Matrix II

문제

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

조건

• $m == matrix.length$
• $n == matrix[i].length$
• $1 \le n, m \le 300$
• $-10^{9} \le matix[i][j] \le 10^{9}$
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• $-10^{9} \le target \le 10^{9}$

예제

Input: 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
Output: true

Input: 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 = 20
Output: false

해결

1st

• 행렬을 다 합쳐버려서 탐색하면? 일단 정렬이 깨지므로 이진 탐색은 쓸 수 없게 된다.
• 한 row씩 탐색하면 되지 않을까?

1 코드

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    if len(matrix) == 0:
        return False
    
    row_len = len(matrix[0])
    idx = -1
    while matrix:
        row = matrix.pop(0)
        left = 0
        right = row_len - 1
        while left <= right:
            mid = left + (right - left) // 2
            if row[mid] > target:
                right = mid - 1
            elif row[mid] < target:
                left = mid + 1
            else:
                idx = mid
                break
        if idx != -1:
            return True
    
    return False

1 결과: 성공

Runtime: 156 ms, faster than 92.11% of Python3 online submissions for Search a 2D Matrix II.
Memory Usage: 19.1 MB, less than 99.94% of Python3 online submissions for Search a 2D Matrix II.

생각보다 빠른 시간이라 놀랐지만, 반대로 더 빠르게 할 수도 있을 거 같다

2nd 책 풀이

2 코드

def searchMatrix2(self, matrix: List[List[int]], target: int) -> bool:
    if len(matrix) == 0:
        return False
    matrix_len = len(matrix) - 1
    row = 0
    col = len(matrix[0]) - 1

    while row <= matrix_len and col >= 0:
        if target == matrix[row][col]:
            return True
        
        if target < matrix[row][col]:
            # 더 작은 값과 비교하기 위해 열을 좌측으로 이동
            col -= 1
        elif target > matrix[row][col]:
            # 더 큰 값과 비교하기 위해 행을 아래로 이동
            row += 1
    return False

2 결과: 성공

Runtime: 168 ms, faster than 41.53% of Python3 online submissions for Search a 2D Matrix II.
Memory Usage: 19.2 MB, less than 99.94% of Python3 online submissions for Search a 2D Matrix II.

생각만큼 빠르지가 않고, 첫번째 시도 코드를 다시 돌려도 대동소이하다 코드 자체보다는 오히려 리트코드 서버의 실행 속도에 좌우되는 느낌

3rd 책 풀이

3 코드

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

• 훨씬 직관적이고, 속도도 나쁘지 않다.
• java, go, python, php 등으로 개발하고 문제를 풀면서 드는 생각이지만, 어지간해서는 built-in 함수의 성능을 넘어서는 것은 불가능한 것 같다. python의 내장 정렬이나 탐색 함수들은 c언어로 작성되어 있는데, 이를 python 코드로 넘는 건 불가능 아닐까? 그러면 결국 해당 언어를 빌드하는 언어 단으로 내려 가야 개선이 가능하다는 건데…
• 따라서 속도는 크게 신경 쓰지 말고, 다양한 풀이와 그 로직 이해에 중점을 둬야 할 거 같다

3 결과: 성공

Runtime: 164 ms, faster than 62.63% of Python3 online submissions for Search a 2D Matrix II.
Memory Usage: 20.6 MB, less than 29.46% of Python3 online submissions for Search a 2D Matrix II.