99클럽 코테 스터디 22일차 TIL(6월 11일) + 알고리즘 이분탐색

[문제 링크]

https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/description/

 

[문제 사고]

주어진 이중 배열을 순회하며 각 요소별로 이분 탐색을 통해 조건에 맞는 요소의 개수를 반환한다.

 

[문제 해결]

Solution - 1
1. 정답을 반환할 임의의 변수 answer을 선언하고 0을 할당한다.
2. grid 배열을 순회하며 각 요소인 내부 배열에 하나씩 접근한다.
3. 각 배열마다 이분 탐색을 진행한다.
4. 이분 탐색을 통해 내부 배열의 요소가 음수인 경우 answer을 1씩 증가해준다.
5. 정답 answer을 반환한다.

Solution - 2
1. 정답을 반환할 임의의 변수 answer을 선언하고 0을 할당한다.
2. 이중 반복문을 통해 이중 배열을 순회하며 각 요소의 값이 음수인 경우 answer의 값을 증가시키는 삼항 연산식을 작성한다.
3. 정답 answer을 반환한다.

 

[작성 코드]

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function(grid) {
    //sol - 1
    let answer = 0
    for(const value of grid){
        let lo = 0
        let hi = value.length - 1
        while (lo <= hi){
            const mid = Math.floor(lo + (hi - lo) / 2 )
            if (value[mid] < 0){
                answer += hi - mid + 1
                hi = mid - 1
            }else{
                lo = mid + 1
            }
        }
    }
    return answer
    //sol - 2
    let answer = 0;
    for(let i = 0; i<grid.length;i++){
        for(let j = 0; j<grid[0].length;j++){
            grid[i][j] < 0 ? answer++ : null
        }
    }
    return answer;
};

 

[문제 회고]

이분 탐색의 풀이에 대해 좀 익숙해져서 이분 탐색 알고리즘을 사용하는데에 어려움은 없었지만 디테일 함이 부족하다는 것을 느꼈다. 또한 이분 탐색보다 이중 반복문을 통해 구현을 하였을 때 더 효율적으로 보였지만 시간 복잡도와 공간 복잡도를 따져보며 다시 공부를 해보며 이분 탐색의 장점을 생각해 볼 필요성을 느꼈다.