[Matrix][Medium] 240. Search a 2D Matrix II

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

 

Q. 주어진 행렬 m x n 이 아래와 같은 조건과 함께 주어질 때, target 값이 행렬내에 있는지 조회하라.

 각 열과 행은 각각 오름차순으로 정렬되어 있다. 

 

 

Solution. 

 정렬되어 있으므로 binary tree를 쓰는 방법으로 가야 최적해가 나올 것 같다. 

 해당 열이나 행의 첫 값이 target보다 더 큰 값이면 해당 열이나 행은 조회에서 제외할 수 있다.  

 

 위 그림에서 x 축은 index 1(4)까지만, y 축은 index 2(3)까지만 target을 조회하면 되는 원리다. 

 

C# 

bool searchValueBST(int[][] matrix, int y, int left, int right, int target)
{
    if(left > right)    return false;

    int mid = left + (right-left)/2;
    if(matrix[y][mid] == target)        return true;

    if(matrix[y][mid] < target)    
        return searchValueBST(matrix, y, mid+1, right, target);
    else 
        return searchValueBST(matrix, y, left, mid-1, target);
}
public bool SearchMatrix(int[][] matrix, int target) 
{
    int yLimit = 0;
    for(int k = 0; k < matrix.Length; ++k, ++yLimit)
    {
        if(matrix[k][0] > target)   break;
    }
    int xLimit = 0;
    for(int k = 0; k < matrix[0].Length; ++k, ++xLimit)
    {
        if(matrix[0][k] > target)   break;
    }

    // binary search.
    for(int k = 0; k < yLimit; ++k)
    {
        if(searchValueBST(matrix, k, 0, xLimit-1, target))
            return true;
    }
    return false;
}

 

범위 안에는 들었지만, 조금 느리다. 

다른 최적해는 어떤 식으로 풀었나 조금 찾아 본다. 

 

 

 

지그재그 방법을 사용했다. 

이 직관은 얻는것이 이 문제의 핵심이겠다. 음.

c#
    
public bool SearchMatrix(int[][] matrix, int target) 
{
    int y = matrix.Length-1;
    int x = 0;
    while(y>=0 && x<matrix[0].Length)
    {
        if(matrix[y][x] == target)  return true;
        if(matrix[y][x] > target)   --y;
        else ++x;
    }
    return false;
}

 

풀이도 심플하다. 

 

좋은 결과를 얻었다.