[Leetcode] 240. Search a 2D Matrix II

문제)

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

 

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

 

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matix[i][j] <= 109
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -109 <= target <= 109

풀이)

1. 내가 푼 방법

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

1. 설명

 정말 생각나는대로 풀었다. 정말 단순하게 for문만 돌려서 품.

 1) 배열의 길이가 1인 경우 아래의 for문이 돌지 않기 때문에, if (matrixLen == 1)을 통해 예외처리 시도.

 2) 2차원 배열의 값들이 오름차순 정렬이 되어있기 때문에, column의 값이 크면 break를 걸어서 다음 row를 찾게하고, row의 첫번째 값이 target 보다 크면, 더 이상 검색할 필요가 없기 때문에 바로 false를 넘겨준다.

 

2. 채점결과

3. 시간복잡도

 배열에 target이 없는 경우, for문이 두 번 돌기 때문에, O(n²)의 시간복잡도를 갖는다.

 

2. 대표 풀이

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

1. 설명

첫번째 row의 column의 끝에서부터 target을 찾는방식.

column과 row가 모두 오름차순 정렬이 되어있기 때문에 가능한 방식.

 1) matrix의 특정 위치의 값이 target보다 작으면, 왼쪽으로 이동,

 2) target보다 크면 오른쪽으로 이동

위와 같은 방식으로 원하는 값을 찾아가는 방법

 

2. 채점 결과

3. 시간복잡도

loop를 한 번 돌고, column과 row의 폭을 좁혀가는 방식이기 때문에, O(n+m)의 시간복잡도를 갖는다.