[LeetCode] 74 Search a 2D Matrix JavaScript

문제 링크

Search a 2D Matrix - LeetCode

 

문제 유형

2차원 배열

 

문제 풀이

이 문제는 정렬된 2차원 m x n 배열내에 target이 있으면 true, 없으면 false를 반환하는 문제이다.
정렬된 1차원 배열을 먼저 생각해보자. 정렬된 1차원 배열에서 어떤 값을 탐색할 때 이진 탐색을 이용하면 O(log n)의 시간복잡도로 문제 해결이 가능하다.
문제에서 주어지는 2차원 매트릭스는 각 행, 열의 숫자들이 모두 오름차순으로 정렬되어 있는 것을 알 수 있다. 따라서 주어진 2차원 배열을 정렬된 1차원 배열로 만들 수 있고, 1차원 배열에 이진 탐색을 수행하면서 2차원 배열의 인덱스와 매칭시키면서 target 값이 있는지 확인하면 된다.

다음과 같은 2차원 매트릭스가 주어졌다고 하자. 이를 1차원 배열로 만들고, high 포인터가 low 포인터를 역전할 때까지 target 값을 찾는 과정을 반복한다.

첫 중간값 인덱스는 5이다. 1차원 배열을 열의 개수만큼씩 자르면 2차원 배열이 나온다. 따라서 현재 인덱스에서 열의 개수를 나누면 행의 위치가 나오고, 현재 인덱스에서 열의 개수를 나눴을 때의 나머지가 열의 위치가 된다. 중간값의 2차원 배열에서의 위치를 구하고 그 값을 target과 비교한다.

11은 타겟값 3보다 크므로 탐색할 지점을 중간값보다 작은 범위로 옮기고, 위의 과정을 또 반복한다.

5는 타겟값 3보다 크므로 탐색할 지점을 중간값보다 작은 범위로 옮기고, 위의 과정을 또 반복한다. 중간값은 target값과 같으므로 true를 반환한다. 만약, 이진 탐색 과정이 끝났는데도 target값이 없으면 false를 반환한다.

 

코드

var searchMatrix = function(matrix, target) {
    const row = matrix.length, col = matrix[0].length;
    let low = 0, high = row * col - 1;
    
    // 2차원 배열을 1차원 배열이라고 생각하고 이진 탐색 수행
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const num = matrix[Math.floor(mid / col)][mid % col];
        
        if (num === target) return true;
        else if (num > target) high = mid - 1;
        else low = mid + 1;
    }
    return false;
};

 

참고

https://www.youtube.com/watch?v=4-y6eGUY-sI