참고
문제해설
NOTE
•
입력 값 ⇒ m * n 크기의 2차원 배열과 정수값
◦
각 행은 내림차순 정렬
◦
각 행의 1번째 정수는 이전 행의 마지막보다 크다.
•
출력값 ⇒ 해당 정수가 2차원 배열에 포함되는가 여부
문제 로직고민
NOTE
세로 방향 → 가로 방향순으로 탐색
•
모든 행렬이 정렬되어 있으므로 Binary Search를 사용한다.
◦
세로 방향의 BinarySearch를 진행한다.
▪
세로 방향의 경우, 정확한 검색이 아닌 범위 탐색을 목적으로 한다.
▪
BinarySearch의 경우 값을 찾지 못하면, left + 1의 값이 나온다. 이 경우 left + 1의 행렬 범위에서 값을 탐색하면 된다.
▪
만약 left + 1의 값이 m과 같거나 커진다면, 모든 값보다 크므로 false를 반환한다.
◦
가로 방향의 BinarySearch를 진행한다.
▪
세로 방향에서 탐색한 행을 가로 방향으로 Binary Search를 진행한다.
▪
여기서는 정확한 값을 찾아야한다.
작성코드
NOTE
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
// 세로방향 탐색
int left = 0;
int right = m-1;
while(left <= right){
int center = (right+left) / 2;
if(target > matrix[center][n-1]) left = center + 1;
else if(target == matrix[center][n-1]) return true;
else right = center -1;
}
// 가로 방향 탐색
int find_m = left;
left = 0;
right = n-1;
// 모든 행렬값보다 큰 경우 값이 존재하지 않는다
if(find_m >= m) return false;
while(left <= right){
int center = (right+left) / 2;
if(target > matrix[find_m][center]) left = center + 1;
else if(target == matrix[find_m][center]) return true;
else right = center -1;
}
return false;
}
}
Java
복사
정답코드
NOTE
class Solution {
public boolean searchMatrix(int[][] a, int target) {
int n=a.length;
int m=a[0].length;
int p1=0,p2=m-1;
while(p1<n && p2>=0){
if(a[p1][p2]==target){
return true;
}
else if(a[p1][p2]<target){
p1++;
}
else{
p2--;
}
}
return false;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
메모리를 가장 절약한 코드인데, 이 경우 최악의 상황에 m*n의 시간복잡도가 걸리므로 최선의 코드는 아닌거 같다.
◦
ex) 찾으려는 값이 m-1행 1번째에 있는 경우