[LeetCode] 74. Search a 2D Matrix

https://leetcode.com/problems/search-a-2d-matrix

개요

1. 2차원 오름차순 배열과 target이 주어진다.
2. target이 배열에 있으면 해당 인덱스를 반환하고, 그렇지 않은 경우 삽입될 인덱스를 반환해라
3. 시간복잡도는 O(log(m * n)) 이내여야 한다.

문제 해결 아이디어

• 오름차순 되어 있으므로, target 이 있을법한 범위를 줄여나가는 방법이 가능하다.
  
  - 2차원 배열이지만, 1차원 배열같이 인덱스를 변환할 수 있다. ex> nums[1][0] = nums[5]

🤨 이진 탐색을 이용하자

➡️ 이진 탐색에는 인덱스 연산이 필요한데, 1차원 인덱스 연산을 통해 보다 수월하게 연산할 수 있다.

의사 코드

1. 1차원 인덱스라고 가정하고, left를 맨 앞 인덱스로, right 을 맨 뒤 인덱스로 할당한다.
2. left와 right의 중간 인덱스를 계산한다.
3. 중간 인덱스를 2차원 인덱스로 변환한다.
4. 2차원 인덱스의 값이 target보다 작다. (조건)
   4-1. left = 중간 인덱스 + 1
5. 2차원 인덱스의 값이 target보다 크다. (조건)
   5-1. right = 중간 인덱스

left = 0
right = (배열 행 개수)*(배열 열 개수) - 1
while(left < right){
	중간인덱스 = (right + left) / 2
    if(matrix[중간인덱스/(배열 열 개수)][중간인덱스%(배열 열 개수)]  < target){
    	left = 중간인덱스 + 1
    }else if(matrix[중간인덱스/(배열 열 개수)][중간인덱스%(배열 열 개수)] < target) {
    	right = 중간인덱스
    } else return true
}
return false

결과

전체 코드 github 링크

다른 풀이

 public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int mid_val = matrix[mid / n][mid % n];

            if (mid_val == target)
                return true;
            else if (mid_val < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }

나와 동일한 방식으로 문제를 풀이한 것 같다.