[LeetCode] - 74. Search a 2D Matrix

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Search a 2D Matrix" 문제입니다.

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

 

문제 : 

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
• -10^4 <= matrix[i][j], target <= 10^4

---

이 문제는 주어진 m x n 정수 행렬에서 각 행은 오름차순으로 정렬되어 있으며, 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 큽니다. 주어진 정수 target이 행렬에 존재하는지 확인합니다. 이 문제는 O(log(m * n)) 시간 복잡도로 해결해야 합니다.

제 코드 바로 보시겠습니다 : 

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean containsTarget = false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    containsTarget = true;
                }
            }
        }
        return containsTarget;
    }
}

 

이 코드를 설명해드리겠습니다 : 

1. 변수 초기화:
   • containsTarget 변수는 target이 행렬에 존재하는지 여부를 저장합니다.
2. 이중 for 루프를 통한 행렬 순회:
   • 첫 번째 for 루프는 행렬의 각 행을 순회합니다.
   • 두 번째 for 루프는 각 행의 각 열을 순회합니다.
   • matrix[i][j]가 target과 일치하면 containsTarget을 true로 설정합니다.
3. 결과 반환:
   • containsTarget 값을 반환하여 target이 행렬에 존재하는지 여부를 반환합니다.

시간 및 공간 복잡도 분석:

1. 시간 복잡도:
   • 이중 for 루프를 사용하여 행렬의 모든 요소를 순회하기 때문에 시간 복잡도는 O(m * n)입니다. 여기서 m은 행렬의 행 수, n은 열 수입니다.
2. 공간 복잡도:
   • 추가적인 메모리 사용이 거의 없으므로 공간 복잡도는 O(1)입니다.

하지만 ! 이 문제는 시간복잡도가 O(log(m*n))인 코드를 원합니다. 저는 그것을 지키지 못하였죠. 하지만, 팁을 드리자면 시간 복잡도가 O(log...)인 문제들은 대부분 이진 탐색을 사용한다는 겁니다. 바로 적용시켜 봤습니다 : 

---

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

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

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

        return false;
    }
}

 

이렇게 똑같은 아이디어지만 이진 탐색을 활용하여 더욱 효율적이게 코드를 개선시켜봤습니다.

---

Runtime 결과