반응형
문제
Write an efficient algorithm that searches for a value in an m x n matrix. This 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.
Example :
Consider the following matrix:
]
Given target = 5, return true.
Given target = 20, return false.
풀이
주어진 matrix에서 target 값이 존재하는 지를 찾는 문제이다.
나는 이진 탐색 트리 이용해 row마다 target 값이 있는지 찾는 방법으로 풀었다. 이렇게 풀면 시간 복잡도가 O(mlogn)이다.
func searchMatrix(matrix [][]int, target int) bool {
if matrix == nil {
return false
}
for _, row := range matrix {
if binarySearch(row, target) {
return true
}
}
return false
}
func binarySearch(row []int, target int) bool {
first := 0
last := len(row) - 1
middle := 0
for first <= last {
middle = (first + last) / 2
if row[middle] == target {
return true
}
if row[middle] > target {
last = middle - 1
} else {
first = middle + 1
}
}
return false
}
Discuss에서 보니 O(m+n)로 푸는 방법도 있다.
우측 상단에서 시작하거나 좌측 하단에서 탐색을 시작하면 된다. 이미지를 보면 이해가 갈 것이다.
아래의 코드는 우측 상단에서 탐색을 시작하는 코드이다.
현재 위치의 값이 target 값보다 작으면 해당 row의 모든 값은 target보다 작다. 각 row는 정렬되어 있으니깐 말이다.
그러므로 아래 row로 이동하면 된다.
현재 위치의 값이 target 값보다 크면 column의 값을 하나 빼서 왼쪽 위치로 이동한다.
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
rowSize, columnSize := len(matrix), len(matrix[0])
row, column := 0, columnSize-1
for row < rowSize && column >= 0 {
if matrix[row][column] > target {
column--
} else if matrix[row][column] < target {
row++
} else {
return true
}
}
return false
}