[LeetCode] Search A 2d Matrix II

문제링크

Search a 2D Matrix II - LeetCode

 

행을 기준으로도 열을 기준으로도 모두 오름차순으로 정렬된 2차원 배열이 있다.
이때 주어진 target 숫자가 행렬에 존재하는지 구하여라.

접근 방법

-10^9 <= matrix[i][j] <= 10^9 크기의 매우 큰 배열이므로 forEach, includes를 사용한 O(n^2) 방법으로는 시간초과가 나온다.

행으로도 열로도 오름차순을 만족하는 배열이므로 정리하자면 아래와 같다.

왼쪽 상단 끝 : 가장 작은 수
오른쪽 상단 끝 : 0행중 가장 크고 마지막 열 중 가장 작은 수
왼쪽 하단 끝 : 0열중 가장 크고 마지막 행 중 가장 작은 수
오른쪽 하단 끝 : 가장 큰 수

가장 큰수와 가장 작은 수인 경우 target값과 비교했을때 행을 이동할지, 열을 이동할지 선택하는데 또 조건이 필요하여 복잡하다. (matrix[0][0] < target 인 경우 matrix[0][1]로 이동할지 matrix[1][0]으로 이동할지 애매하다.)

때문에 오른쪽 상단 끝 또는 왼쪽 하단 끝부터 이동해야지 깔끔하게 문제를 풀이할 수 있다.

const rowLen = matrix.length;
const colLen = matrix[0].length;

let curRow = rowLen - 1;
let curCol = 0;​

이번 풀이는 왼쪽 하단 끝부터 시작하였다. (오른쪽 상단 끝은 curRow = 0; curCol = colLen - 1; 로 바꾸면 됨)

while(curRow >= 0 && curCol < colLen){
    const curVal = matrix[curRow][curCol];

    if(curVal > target){
        curRow--;
    }else if(curVal < target){
        curCol++;
    }else{
        return true;
    }
}

matrix 범위 내에서
1. target 값이 현재 값보다 작으면 행을 하나 줄인다.

2. target 값이 현재 값보다 크면 열을 하나 키운다.

3. 같으면 target값을 발견하였으므로 true를 반환한다.

4. 범위에서 벗어나면 false를 반환한다.

 

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    
    let curRow = rowLen - 1;
    let curCol = 0;
    
    while(curRow >= 0 && curCol < colLen){
        const curVal = matrix[curRow][curCol];
        
        if(curVal > target){
            curRow--;
        }else if(curVal < target){
            curCol++;
        }else{
            return true;
        }
    }
    
    return false;
};