Search a 2D Matrix
행이 m개이고 열이 n개인 정수 격자 matrix와 정수 target이 주어집니다. 각 행은 오름차순으로 정렬되어 있으며, 각 행의 첫 번째 값은 그 위 행의 마지막 값보다 큽니다. target이 격자에 있으면 true를, 그렇지 않으면 false를 O(log(m × n)) 시간에 반환하세요.
함수
- matrixinteger-2d-array
- 행별로 정렬된 행 목록으로 주어지는 그리드
- targetinteger
- 찾을 값
- 반환값boolean
- true if target가 그리드에 있으면, 그렇지 않으면 false
제약 조건
1 ≤ m, n ≤ 100, 여기서m = matrix.length이고n = matrix[i].length입니다.- 모든 행의 길이는 동일하게
n입니다. -104 ≤ matrix[i][j], target ≤ 104- 각 행은 엄격한 오름차순으로 정렬되어 있으며, 각 행의 첫 번째 값은 이전 행의 마지막 값보다 큽니다.
예제
- 입력
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- 출력
- true
- 설명
- 행을 순서대로 읽으면 12개의 값은 하나의 정렬된 목록입니다. 위치 0부터 11까지 이진 검색을 수행하면 위치 5의 21(너무 작음), 위치 8의 33(너무 큼)을 확인한 다음 위치 6에서 26을 찾습니다.
- 입력
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- 출력
- false
- 설명
- 16은 0행의 마지막 값인 14 다음에, 1행의 첫 번째 값인 17 앞에 옵니다. 그 사이에는 아무것도 없으므로 16은 그리드에 없습니다.
후속 질문
행의 길이가 서로 다르더라도 처음부터 끝까지 정렬되어 있다고 가정해 봅시다. 위치를 행과 열로 어떻게 변환할 수 있을까요? 검색 비용은 얼마나 들까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
행렬을 하나의 긴 목록인 것처럼 왼쪽에서 오른쪽으로, 행별로 읽어 보세요. 그 목록에 있는 값의 순서에서 무엇을 알 수 있나요?
두 규칙을 함께 적용하면 행별로 읽은 전체 행렬은
m × n개의 값으로 이루어진 하나의 정렬된 목록이 됩니다. 이 목록을 실제로 만들지 않고도 이진 탐색을 할 수 있습니다.0부터m × n - 1까지의 위치에서 이진 탐색을 합니다. 위치p는 행p / n과 열p % n(정수 나눗셈)에 해당하므로, 각 단계에서 셀 하나를 읽고 남은 위치의 절반을 버립니다.
풀이
두 가지 정렬 규칙을 함께 적용하면, 격자를 행별로 읽었을 때 m × n개의 값이 정렬된 하나의 목록이 됩니다. 위치를 기준으로 이 목록을 이진 검색한 다음, 나눗셈 한 번으로 각 위치를 행과 열로 다시 변환하세요. 그러면 100×100 격자에서 비교 횟수가 10000회가 아니라 최대 14회면 됩니다.
모든 셀을 확인하세요
핵심 아이디어
모든 셀을 target과 비교하고 일치하면 true를, 마지막 셀까지 확인한 후에도 일치하는 셀이 없으면 false를 반환합니다. 모든 셀을 읽으므로 정렬 여부와 관계없이 어떤 그리드에서도 올바르게 작동합니다. 순서를 전혀 활용하지 않으므로 100 x 100 그리드에서는 최대 10000번의 비교가 필요합니다.
알고리즘
matrix의 각 행에서 각 값을 순서대로 살펴봅니다.- 값이
target과 같으면true를 반환합니다. - 반복문이 끝난 후
false를 반환합니다.
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return False오른쪽 위 모서리에서 걸어가세요
핵심 아이디어
오른쪽 위 셀에서 왼쪽으로 갈수록 값이 작고 아래로 갈수록 값이 큽니다. 셀의 값이 target보다 크면 그 아래 열의 값도 더 큽니다. 왼쪽으로 이동해 해당 열을 제외하세요. 값이 더 작으면 왼쪽 행의 값도 더 작습니다. 아래로 이동해 해당 행을 제외하세요.
첫 번째 예시에서 14는 26보다 작으므로 아래로 이동해 30으로 갑니다. 30은 더 크므로 왼쪽으로 이동해 26에 도달하고, 일치합니다. 이동할 때마다 행이나 열 하나가 제거되므로 최대 m + n번 이동합니다. 100×100 격자에서는 200번입니다. 이 탐색은 행과 열이 정렬되어 있기만 하면 되므로, 이 격자가 제공하는 정보의 절반은 사용하지 않습니다.
알고리즘
- 행
0과 마지막 열에서 시작합니다. - 행과 열이 격자 안에 있는 동안 셀을 읽습니다.
- 그 값이
target과 같으면true를 반환합니다. - 그 값이 더 크면 열을 하나 왼쪽으로 이동하고, 더 작으면 행을 하나 아래로 이동합니다.
- 격자 밖으로 나가면
false를 반환합니다.
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return False평탄화된 그리드에서의 이진 탐색
핵심 아이디어
셀에 행별로 번호를 매깁니다. 0번 행에는 위치 0부터 n - 1까지, 1번 행에는 n부터 2n - 1까지 들어가며, 이런 식으로 이어집니다. 각 행은 정렬되어 있고 이전 행이 끝난 위치보다 높은 곳에서 시작하므로, 위치가 커질수록 값도 커집니다. 이는 정렬된 목록이므로 이진 탐색을 적용할 수 있습니다.
목록을 직접 만들지는 않습니다. 위치 p는 정수 나눗셈을 사용해 행 p / n, 열 p % n에 있습니다. 첫 번째 예시에서 n = 4이므로 위치 6은 행 1, 열 2에 있으며, 여기에 26이 들어 있습니다. 비교할 때마다 target이 있을 수 있는 위치의 수가 절반으로 줄어듭니다. 10000개의 셀이 있을 때 비교 횟수는 최대 14회이며, 추가 메모리는 인덱스 두 개만 사용합니다.
알고리즘
m과n을 각각 행과 열의 개수라고 하고,lo = 0,hi = m × n - 1로 설정합니다.lo ≤ hi인 동안 두 값의 중간에 있는mid를 구합니다.value = matrix[mid / n][mid % n]을 읽습니다.value가target과 같으면true를 반환합니다. 더 작으면lo = mid + 1로 설정하고, 그렇지 않으면hi = mid - 1로 설정합니다.- 루프가 끝나면
false를 반환합니다.
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
함정과 경계 사례
- 열이 아니라 행의 개수로 나누는 경우. 위치
p는 행p / n에 있습니다. 그 자리에m을 사용하면 정사각형 격자에서는 코드가 통과하지만, 3행 4열에서는 실패합니다. - 두 번 검색하는 버전에서
matrix[0][0]보다 작은target을 처리하지 않는 경우. 그 값 이하에서 시작하는 행은 없으며, 행 인덱스-1이 두 번째 검색으로 넘어갑니다. - 포함된
hi를 사용하면서lo < hi조건으로 반복하는 경우.target을 담은 1×1 격자는 반복문이 실행되지 않으므로false를 반환합니다. - Lua와 R에서 인덱스를 1부터 시작하도록 조정하는 것을 잊는 경우: 위치
p는 행p / n + 1, 열p % n + 1입니다.
자주 묻는 질문3
2차원 행렬 검색의 시간 복잡도는 얼마인가요?
평탄화된 그리드에서의 이진 검색은 O(log(m × n)) 시간과 O(1) 공간을 사용합니다. 10000개의 셀에서는 비교 횟수가 최대 14회입니다. log(m × n) = log m + log n이므로, 행을 찾은 다음 그 행 안에서 검색하는 것과 같습니다.
오른쪽 위 모서리부터 시작하는 탐색과 이진 탐색 중 무엇을 사용해야 할까요?
모서리 탐색은 O(m + n) 단계가 걸리고 행과 열이 정렬되어 있기만 하면 되므로, 한 행이 위 행의 끝보다 아래에서 시작할 수 있는 변형 문제도 해결합니다. 여기처럼 각 행이 이전 행이 끝나는 위치보다 위에서 시작하는 경우에는 이진 탐색이 더 빠릅니다.
행을 찾는 이진 탐색과 그 행 안에서 수행하는 이진 탐색, 이렇게 두 번의 이진 탐색을 하는 것도 올바른가요?
네. 첫 번째 열에서 첫 번째 값이 target 이하인 마지막 행을 이진 탐색한 다음, 해당 행을 이진 탐색하세요. 실행 시간은 O(log m + log n)으로 동일한 시간 복잡도입니다. 한 번의 탐색으로 같은 작업을 수행하면서 루프 하나만 사용하고 예외 상황도 줄일 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def searchMatrix(matrix, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
예상 출력
true