LeetCode 74(Search a 2D Matrix, java)

0. 문제

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

Search a 2D Matrix - LeetCode

 

1. 문제 설명

- 문제에서 이중 배열(matrix)과 찾고자 하는 숫자(target)가 주어진다.

- 이중 배열의 규칙과 구조를 파악하여 target을 찾는 가장 효율정인 탐색 알고리즘을 작성하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 우선 문제에서 주어지는 이중 배열(matrix)의 구조와 규칙을 파악한다.

  → 각 행마다 오름차순으로 원소가 나열된다.

  → 각 행의 첫 번째 원소는 이전 행의 마지막 원소보다 크다.

 

b) 두 번째 접근

- 위의 규칙을 이용하면 찾고자 하는 숫자를 탐색하는 알고리즘을 쉽게 작성할 수 있다.

 

- 우선 찾고자 하는 숫자가 몇 번째 행에 존재하는지를 알아야 한다. 

- 이를 위해서 어떤 행의 첫 번째 원소보다 크고 마지막 원소보다 작은 경우를 찾아야 한다.

 

- 행을 찾은 다음에는 몇 번째 열에 존재하는지를 찾아야 한다.

- 이를 위해서는 이진 탐색을 수행하는 것이 가장 효율적이다.

- 그러나 이 문제에서는 이진 탐색을 사용할 수 없다.

 

- 그 이유는 matrix 내부에 target이 없을 수도 있기 때문이다.

  → target이 존재하지 않는 경우, 무한 비교를 수행한다. 

 

- 그러므로 행을 찾은 다음에는 순차적으로 배열을 탐색해야 한다.

 

- target이 matrix 내부에 존재한다면 true를 반환한다. 

- target이 matrix 내부에 존재하지 않는다면 false를 반환한다. 

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        int row = 0;
        int col = 0;
        
        while(row < matrix.length && col < matrix[0].length) {
            if(matrix[row][col] == target) {
                return true;
            }
            else if(matrix[row][matrix[0].length - 1] < target) {
                row++;
            }
            else col++;
        }
        return false;
    }
}