class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
k = []
for i in range(len(matrix)):
k.append(matrix[i][0])
col = bisect_right(matrix[0], target)
row = bisect_right(k, target)
for i in range(row):
for j in range(col):
if matrix[i][j] == target:
return True
return False
처음 제출한 풀이이다. target보다 큰 row와 col은 제외하고 탐색한다. 하지만 row나 col이 matrix 행열의 길이와 같다면 완전탐색과 다름없다.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# return any(target in row for row in matrix)
if not matrix:
return False
# 0행 마지막 열에서 시작
row = 0
col = len(matrix[0]) - 1
while row <= len(matrix) - 1 and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
elif matrix[row][col] < target:
row += 1
return False
첫 행의 마지막 원소를 시작으로 값을 줄여나가는 풀이이다. 전체적인 코드의 형태가 투 포인터를 사용하는 코드와 비슷하다.
any를 효율적으로 사용하는 예시
# 1차원 배열에서 any
arr = [1, 3, 5, 7, 9]
result = [num > 10 for num in arr]
print(result) # [False, False, False, False, False]
print(any(num > 10 for num in arr)) # False 아래와 동일한 결과
print(any(result)) # False
# 2차원 배열에서 any
arr = [[1, 3, 5, 7, 9], [2, 4, 6, 8, 10]]
ans = [5 in row for row in arr]
print(ans) # [True, False]
print(any(row[0] > 5 for row in arr)) # False
print(any(5 in row for row in arr)) # True
any의 매개변수로 리스트 컴프리헨션을 통해 만들어진 True 또는 False로 구성된 리스트를 사용했다.