[LeetCode] 74. Search a 2D Matrix - Java

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

Search a 2D Matrix - LeetCode

---

문제

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

 

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

---

풀이

풀이 과정

m x n크기의 2차원 배열 matrix가 주어지고 다음과 같은 성질을 가진다.
배열의 각 행은 오름차순 정렬되어 있으며, 각 행의 첫 번째 요소는 이전 행의 마지막 요소보다 큰 값을 가진다.

정수 target이 주어질 때 target이 배열 내에 존재하는 경우 true, 그렇지 않은 경우 false를 return 해야한다.
단, O(log(m x n))의 시간 복잡도로 풀이해야 한다.

---

이진탐색을 2차원 배열에 적용하여 풀이하였다.

먼저 탐색을 시작할 행의 인덱스를 0으로 초기화하고 열의 인덱스는 마지막 값으로 초기화한다.

int row = 0;
int col = matrix[0].length - 1;

 

행의 인덱스가 배열의 길이를 넘지 않고 열의 인덱스가 0 이상인 경우 반복하여 다음 조건을 탐색한다.

• 현재 행,열의 값이 target과 일치하는 경우 true를 return한다.
• 현재 행,열의 값이 target보다 작은 경우, 즉 각 행의 마지막 값이 target보다 커질 때 까지 row를 증가시킨다.
• 현재 행, 열의 값이 target보다 큰 경우, 즉 현재 행이 target이 속할 수 있는 범위 내 인경우 col을 감소시킨다.

while(row < matrix.length && col >= 0) {
    // target과 일치하는 경우
    if(matrix[row][col] == target) return true;
    // 현재 row의 col 값이 target보다 작은 경우 row 증가
    if(matrix[row][col] < target) row++;
    // 현재 row의 col 값이 target보다 큰 경우 col 감소
    else col--;
}

 

모든 탐색이 종료되는 경우에는 target과 일치하는 요소가 없으므로 false를 return 한다.

// 반복 탐색이 모두 끝난 경우 target이 포함되지 않으므로 false를 return
return false;

---

최종 코드

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;
        
        while(row < matrix.length && col >= 0) {
            // target과 일치하는 경우
            if(matrix[row][col] == target) return true;
            // 현재 row의 col 값이 target보다 작은 경우 row 증가
            if(matrix[row][col] < target) row++;
            // 현재 row의 col 값이 target보다 큰 경우 col 감소
            else col--;
        }
        
        // 반복 탐색이 모두 끝난 경우 target이 포함되지 않으므로 false를 return
        return false;
    }
}

---