leetcode, Search a 2D Matrix

• 해당 문제는 파파고 번역을 통해 풀이를 하였습니다.

문제

m x n의 배열에서 값을 검색하는 효율적인 알고리즘을 작성한다.
이 배열에는 다음과 같은 속성이 있다.

• 각 행의 정수는 왼쪽에서 오른쪽으로 정렬된다.
• 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 크다.

예제

예제 1

Input 	: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
	  target = 3
Outpu	: true

예제 2

Input 	: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
	  target = 13
Outpu	: false

초기값

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

나의 풀이

나는 단순하게 생각하였다...
그냥 이중배열(matrix)를 일차원 배열로 만든 다음 값(target)을 찾기만 했다...

런타임은 약 84ms가 나왔고 메모리 사용량은 38.9MB가 나왔다.

var searchMatrix = function(matrix, target) {
  return matrix.flat().some(v => v === target);
}

다른 사람의 풀이

다른사람의 풀이도 궁금하여서 찾아보았다.
해당 자료는 유튜브에서 찾았다.
Code Intern, LeetCode - Search a 2D Matrix - Javascript

런타임은 약80ms가 나왔고 메모리 사용량은 38.7MB가 나왔다.

var searchMatrix = function(matrix,target) {
  if(!matrix.length) {
    return false;
  }
  let i = 0;
  let j = matrix[0].length - 1;
  
  while(i < matrix.length && j >= 0) {
    if(matrix[i][j] > target) {
      j--;
    } else if(matrix[i][j] < target) {
      i++;
    } else {
      return true;
    }
  }
    return false;
  }

후기

완성하고나서 효율적이지 못한 알고리즘이라고 생각했다.
만약, 배열의 길이가 매우 길다고 가정할 경우 값을 찾기 위해 모든 값을 찾아 나설 것이다. 도중 값을 찾았다고 해도 배열의 끝까지 찾기 때문에 속도는 느려질것이다.
시간복잡도를 전혀 고려하지 못하였다.