[leetCode 74번] Search a 2D Matrix (Java)

1.문제

Search a 2D Matrix - LeetCode

Search a 2D Matrix - LeetCode

---

2.문제설명

문제 예시 와 설명을 읽어보면 2차원 배열에 주어진 target 값이 있는지 여부를 찾으면 되는 문제이다 

이 문제의 핵심은 O(long(m*n)) 이라는 제한 사항이 있다.

---

3.소스코드

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
 
    int rows = matrix.length;
    int cols = matrix[0].length;
    int left = 0;
    int right = rows * cols - 1;

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

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

    return false;
}

}

---

4.소스코드설명

 

이 문제는 O(log(M*N)) 이라는 제약 사항이 있어 2중for문으로 search를 한다면 분명 제약사항에 걸릴 것이기 분명하다.

그러한 이유로 이분 탐색을 진행 하면 된다. 

 

기본 1차원 배열에서 이분탐색을 진행 하는 것과 비슷하게 진행하면 된다. 

 

추가 적인 부분은 2차원 배열이 므로 row / col 의 위치와 left / right 의 시작 위치가 필요하다 .

또한 mid 값은 기본 이분탐색 처럼 하지만 mid의 값을 구하기 위해서는 midValue 를 직접 계산 하여 구해줘야한다는 점이다.

 

matrix = [
	[1,3,5,7],
	[10,11,16,20],
	[23,30,34,60]
]

일때

 

[1,  3,  5,  7, 10, 11, 16, 20, 23, 30, 34, 60]

 

예를 들어서 mid 가 5일 경우에는 mid/ cols 5 를 4로 나눈 결과인 1 이값을 row 

mid % cols 로 나눈 나머지를 1 이 나와 이값을 col 

midValue [row][col] = midValue [1][1] -> 11 이라는 중앙값을 찾을 수 있게 된다.

 

---

5.회고

 

익숙한 1차원 배열에서의 이분탐색에서 2차원 배열 이분탐색을 진행할때 mid 값을 정해주는 부분을 다시 한번 상기 시킬수 있는 문제 였다고 생각한다.