Count Negative Numbers in a Sorted Matrix

문제

gird 형태로 n x m 으로 주어진 배열에서 음수인 값을 찾는 문제이다.

접근방법

단순 for loop를 활용해서 구할수 있으나, 문제의 의도는 이진탐색을 사용하여 O(n + m)의 코드를 구현해 내는 것이다. 이진탐색의 기본 풀이법인 다음과 같은 공식을 활용하였다.

1. pivot값을 구한다.
2. pivot값을 토대로 조건에 따라 처음과 끝부터 검색한다.

풀이

이진탐색을 사용한 풀이는 다음과 같다.

var countNegatives = function(grid) {

    let cnt = 0

    grid.forEach((e, i) => {
        let left = 0
        let right = e.length - 1

        while(left <= right){
            //기준점이 될 수 있는 중간값을 찾는다.
            let pivot = Math.floor((left + right) / 2)

            //양수일 경우
            if(e[pivot] >= 0){
                left = pivot + 1
            } else {
                right = pivot - 1
            }
        }
        
      	//left는 배열내의 양수의 최대값을 가르킬 것이다
        cnt += e.length - left //grid 형태이기 때문에 e.length는 loop전에 구해서 사용해도 됨
    })

    return cnt
};

고민한 부분

pivot을 사용하는 while문은 이진탐색에서 자주 쓰이는 공식으로써 문제없이 적용했으나, 배열내에서 음수인 값들을 찾는 부분에서 상당히 골머리를 썩었다. 의외로 단순한데도 불구하고 말이다.

추가로 해결한 문제

추가로 해결한 문제는 sqrt(x)이다. 해당 문제는 음수가 아닌 정수가 주어지고, 제곱근의 가장 가까운 정수로 내림하여 반환하는 것이다. 이때, 기본 제공 함수인 지수 함수 및 연산자를 사용하면 안된다.

코드

var mySqrt = function(x) {
  	//0,1의 결과값은 0,1이다.
    if(x < 2) return x

    let num = 0
    let left = 2
    let right = Math.floor(x/2) // 제곱근은 항상 x/2이하이다.

    while(left <= right){
        pivot = left + Math.floor((right - left) / 2) // 중간 값 구함
        num = pivot * pivot // 제곱근 계산
        if(num > x) right = pivot - 1 
        else if( num < x) left = pivot + 1
        else return pivot
    }

    return right //반복문을 종료한 후 가장 큰 정수 제곱근이 right에 저장되어 있음
};

주의점

기본적으로 사용하는 Math.floor((left+right)/2))의 경우 결과 값이 너무 커서 정수 오버플로우가 날 수 있으므로 left + Math.floor((right - left) / 2)와 같은 공식을 사용하였다. 언제 문제가 발생할지 모르기 때문에 앞으로도 해당 공식이 익숙해질 수 있도록 해야한다.