[LeetCode] Search a 2D Matrix - Javascript

Search a 2D Matrix

[각 행과 열이 오름차순의 값을 가지고 있는 배열이 주어졌을때 target의 존재 여부 반환]

 

제약 조건 

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

 

Example

ex1) Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
     Output: true
     
ex2) Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
     Output: false

초기 문제 접근 방식

이진 탐색 방법으로도 문제가 풀릴 것 같았지만,

가장 먼저 쉽게 풀이 방법이 생각 난 전체 탐색(brute force) 방식으로 먼저 풀어봤다.

2차원 배열에 있는 값들을 모두 반복문으로 순회해 matrix[i][j]의 값이 target과 같다면 true를 반환했다.

초기 전체코드

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
   for (let i = 0; i < matrix.length; i++) {
      for (let j = 0; j < matrix[0].length; j++) {
         if (matrix[i][j] === target) {
            return true;
         }
      }
   }
   return false;
};

 

다시 생각 해보며..

단 위의 방식대로 풀게 되면 시간 복잡도가 O(N)이 나오기에 O(LogN)이 나올 수 있도록 이진 탐색으로도 생각해봤다.

 

맨 처음 m과 n 변수는 각각 matrix 배열의 길이와 matrix[0] 배열의 길이로 초기화한다.
m 배열의 0번 배열의 인덱스와 n은 마지막 배열의 인덱스를 가리키게 하는 것이다.
그 후 while 문을 right 포인터가 크거나 같을 때까지 순회하며,

mid는 배열의 중간 값으로 업데이트해준다.
그 과정에서 mid와 n을 나눈 몫의 값은 r에 저장하고 나머지 값은 c에 저장한다.

matirix[r][c]의 값이 target과 같다면 true를 리턴하고,matirix[r][c]의 값이 더 크다면 right의 값은 mid-1로 업데이트하고,

작다면 left는 mid+1로 업데이트한다.

이렇게 하면 이진 탐색으로 경우의 수를 줄여나가며 배열에 target과 같은 값이 있는지 탐색할 수 있게 된다.

solve 전체 코드

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
   let m = matrix.length;
   let n = matrix[0].length;
   let left = 0; 
   let right = m * n - 1;
   let mid,
      r,
      c = 0;
   while (left <= right) {
      mid = Math.floor(left + (right - left) / 2);
      r = Math.floor(mid / n);
      c = Math.floor(mid % n);

      if (matrix[r][c] == target) {
         return true;
      } else if (matrix[r][c]> target) {
         right = mid - 1;
      } else {
         left = mid + 1;
      }
   }
   return false;
};

 

 

다른 sovle 코드

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    return matrix.flat(1).includes(target)
};

한 줄로 풀이가 가능한 코드가 있어 해당 코드에 대해 알아봤다.
우선 문제에서 사용된 두 개의 메서드에 대해 알아야 한다.

flat(): 하위 배열 요소를 지정한 깊이까지 재귀적으로 새로운 배열로 생성하는 것이다.
includes(): 배열이 특정 요소를 포함하고 있는지 true와 false 형태로 반환해 준다.

const arr1 = [1, 2, [3, 4]];
arr1.flat(1); // default depth: 1
// [1, 2, 3, 4]

만약 위의 코드처럼 arr1 배열에 [1,2, [3,4]]를 넣었다고 가정하고
이것을 flat(1) 해주면 [1,2,3,4] 1차원 배열로 반환이 된다. 이 상태에서 includes[배열]을 사용해 주면 target 값이 해당 배열에 있는지 찾아주고 있으면 true를 반환하고 아니라면 false를 반환하는 것이다.

다만 조금 더 알아본 결과 include()의 시간 복잡도는 O(n)이기에 문제에서의 O(log(n*m)의 복잡도를 충족 시킬 수 없어 완벽한 답이라고 볼 순 없지만, 코드가 한 줄로 해결되는 점을 생각하면 이해하고 읽고 이해하기 쉽기에 해당 방법 또한 알고 있으면 도움 될 것이다.