Search a 2D Matrix

문제

m x n 크기의 정수 행렬이 주어집니다. 이 행렬은 다음 두 가지 특성을 가지고 있습니다.

• 1. 각 행은 오름차순으로 정렬되어 있습니다.
• 2. 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 큽니다.

정수 'target'이 주어졌을 때, 해당 정수가 행렬 내에 있다면 true를, 그렇지 않다면 false를 반환하세요. O(log(m * n))의 시간 복잡도를 가진 해결 방안을 작성해야 합니다.

접근 방향

입출력 예제를 볼 때 matrix가 인수로 들어올 때 첫 번째 배열부터 마지막 배열 안의 요소가 순서대로 오름차순으로 정렬되어 있으므로 새로운 배열을 하나 생성하고 이차원 배열을 순회하면서 배열 안 모든 요소를 새로운 배열에 추가한 뒤 이전의 이분 탐색법과 동일하게 풀이합니다. 하지만 한 가지 다른 점은 이전 문제에서 start를 반환하였다면 이번에는 end를 인덱스로 지정하는 요소와 target을 서로 비교해야 합니다. start 인덱스가 가리키는 요소와 비교할 경우 새로 생성한 배열의 길이보다 start 인덱스가 더 커서 "list index out of range" 에러가 발생할 수 있습니다.

나의 풀이

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """

        # 이차원 배열 안의 배열들이 가진 요소를 하나의 배열로 통합하기 위해
        # 새로운 배열을 생성합니다.
        l = []
        # 이차원 배열을 순회하면서 각 배열이 가진 요소들을 새로운 배열에 추가합니다.
        for row in matrix:
            for i in row:
                l.append(i)

        # 이분 탐색 범위에 사용될 start와 end 변수를 초기화합니다.
        start = 0
        end = len(l) - 1

        while start <= end:
            # 중앙 인덱스 할당
            mid = (start + end) // 2

            # 중앙값이 target보다 클 경우, 오름차순 정렬에서 target이 중앙값보다
            # 왼쪽에 있다는 것을 의미합니다. 따라서 탐색 범위를 중앙값 기준 왼쪽으로 변경합니다.
            if l[mid] > target:
                end = mid - 1
            # 중앙값이 target보다 작을 경우, 오름차순 정렬에서 target이 중앙값보다
            # 오른쪽에 있다는 것을 의미합니다. 따라서 탐색 범위를 중앙값 기준 오른쪽으로 변경합니다.
            elif l[mid] < target:
                start = mid + 1
            else:
                # 중앙값이 target과 일치할 경우, 타겟이 이차원 배열 안에 존재하므로 True 반환
                return True

        # return False로 변경하여도 무관
        return l[end] == target
        # return False

다른 사람의 풀이

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """

        # 행의 개수
        r = len(matrix)
        # 첫 번째 행의 길이
        c = len(matrix[0])
        # 첫 번째 인덱스를 0으로 초기화
        l = 0
        # 전체 행의 개수인 r * c에서 1을 차감할 경우 마지막 행의 마지막 요소를 가리키는 인덱스를 의미
        h = r * c - 1

        # 첫 번째 인덱스인 l이 마지막 인덱스 h보다 작을 때
        while l <= h:
            m = (l + h) // 2
            # 이차원 배열에서의 중앙값 계산
            num = matrix[m//c][m%c]
            # 타겟과 일치한다면 True 반환
            if num == target:
              return True
            # 중앙값이 타겟보다 작다면, 타겟은 오른쪽에 있는 것이므로 범위를 오른쪽으로 변경
            elif num < target:
              l = m + 1
            # 중앙값이 타겟보다 클 경우, 타겟은 왼쪽에 있는 것이므로 범위를 왼쪽으로 변경
            else:
              h = m - 1
        return False

다양한 풀이 중에서 위 사람의 코드를 가져온 이유는 내가 사용한 방식처럼 이차원 배열을 일차원 배열로 변환하는 과정을 거치지 않고 matrix 안에 모든 배열이 오름차순으로 정렬되어 있고 다음 행의 시작 원소가 이전 행의 마지막 원소보다 크다는 조건을 이용하여 이차원 배열을 그대로 사용하였기 때문이다. 위 식에서 특히 "num = matrix[m//c][m%c]" 계산식을 사용해서 이차원 배열에서의 중앙값을 가져온다는 아이디어를 나는 생각치 못하였기 때문에 "이차원 배열에서 중앙값은 이렇게 도출하는구나"라고 느껴졌다.

# 2차원 배열 = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
# 1차원 배열 = [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
m = (0 + 11) // 2 => 5
# 이 때 일차원 배열로 가정한다면 중앙값은 11이 된다.

# 다음은 이차원 배열에서의 중앙값을 도출하는 계산식이다.
num = matrix[5//4][5%4]
num = matrix[1][1] => 11
# 일차원 배열에서와 마찬가지로 이차원 배열에서도 동일하게 요소 11을 중앙값으로 가져온다.