[Leetcode] 74. Search a 2D Matrix

문제 : https://leetcode.com/problems/search-a-2d-matrix/

---

m x n 정수형 배열 matrix 가 있을 때, 아래 2가지 조건을 만족한다.

- 정수는 각 행에서 왼쪽에서 오른쪽으로 오름차순 정렬되어 있다.

- 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 크다.

target 값이 주어질 때, matrix에서 target이 존재하는지 구해라.

---

matrix 의 최상당 최우측에 있는 요소부터 탐색해나간다. 탐색중인 인덱스를 row, col 이라 하자.

 

만약 matrix[row][col]이 target과 같다면 target이 존재한다는 뜻이므로 true를 반환한다.

만약 matrix[row][col]이 target보다 크다면 col을 1 감소시킨다.

만약 matrix[row][col]이 target보다 작다면 row를 1 증가시킨다.

 

row, col이 matrix 배열 범위를 벗어날 때까지 target 값을 찾지 못한다면 false를 반환한다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/74.%20Search%20a%202D%20Matrix.cpp

---

어딘가 많이 본 문제다 했는데 예전에 푼 240. Search a 2D Matrix 2 랑 동일한 풀이법으로 해결 가능하다. 설명한 내용이 이해가지 않는다면 해당 포스팅을 참고바란다.