📑 문제
주어진 정수(target)가 이 행렬에 존재하는지 확인해야 합니다. 만약 존재하면 true를, 그렇지 않으면 false를 반환해야 합니다.
m x n 크기의 정수 행렬(matrix)가 주어지며, 이 행렬은 다음 두 가지 조건이 있습니다.
1. 각 행은 비감소 순서로 정렬되어 있습니다.
2. 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 큽니다.
단, 시간 복잡도가 O(log(m * n))인 알고리즘을 작성해야 합니다
📑 접근 방법
처음에는 선형탐색을 활용하여 풀었습니다.
전체 배열을 흝어보고 target과 같다면 true를 출력하는 형식으로 구현했습니다.
하지만 이렇게 구현할 경우 O(n)이 되어서, 주어진 조건 중하나인 시간복잡도 조건을 만족하지 못합니다.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
boolean isTrue = false;
for(int i = 0 ;i < matrix.length; i++){
for(int j= 0 ; j<matrix[i].length; j++){
if(matrix[i][j]==target){
isTrue = true;
}
}
}
if (matrix.length == 0) {
return false;
}
return isTrue;
}
}그래서 이분 탐색을 활용하여 문제를 해결했습니다.
left와right포인터를 초기화하여 2차원 배열을 1차원 배열처럼 처리하는데, 이때 left와 right는 배열의 시작과 끝을 가리킵니다.left가right보다 작거나 같은 동안 반복문을 실행합니다.- 중간 인덱스
mid를 찾습니다. (left와right의 평균값) - 이 중간 인덱스를 행렬의 행과 열로 변환하여 해당 위치에 있는 값 ( =
midValue) 를 얻습니다. midValue값이 타겟 값과 같다면 타겟값을 찾은 것이므로 true를 반환합니다.- 만약 이
midValue값이 타겟 값보다 작다면, 타겟 값은 오른쪽 하위 배열(중간값부터 끝까지)에 있어야 하므로left=mid+ 1;. - 만약 이
midValue값이 타겟 값보다 크다면, 타겟 값은 왼쪽 하위 배열(시작부터 중간값까지)에 있어야 하므로right=mid- 1; - 모든 요소를 검사한 후에도 찾지 못했다면 false를 반환합니다.
📑 CODE
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int left = 0;
int right = matrix.length * matrix[0].length -1;
while(left <= right){
int mid = (left + right) / 2;
// 중간 위치의 행열 구하기
int midVal = matrix[mid/matrix[0].length][mid%matrix[0].length];
if(midVal == target) return true;
else if(midVal < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
}