Question

(정답주의) JS 풀이 공유 및 왜 이진탐색 문제인가?

처음에 문제를 보고 for문을 통해서 stones값을 -1씩 반복 및 접근해서 *조건을 따진다면 시간복잡도가 당연히 통과하지 못할 것이라고 생각했다.

그래서 고안한 방법은 stones의 값 중 0이 아닌 최솟값을 찾아서 최솟값만큼 빼주면 되지 않을까 라고 생각했다.
하지만 최솟값을 구하기 위해서는 역시 stones를 (max:20000)만큼 반복 순회하여야 했다.
이때 Math.min()함수를 사용했는데 매개변수로 20000개의 원소가 입력되면 런타임 에러가 뜬다.

문제 풀이의 핵심 접근은 임의의 값을 stones의 모든 값에서 감소시킨 후 *조건을 따져주는 방식으로 푸는 것이다.

여기서 반복문을 사용해서 임의의 값을 정한다면 (max: 200,000,000) 당연히 시간복잡도를 만족 할 수 없다.

따라서 이진탐색 O(log N)을 통해서 문제를 해결하는 생각이 떠오른다. (min = 1, max = 200,000,000)

*조건 : stones에서 중복되는 0이 k >= 0 인가

작성중인 코드―solution.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function solution(stones, k) {
    // 이분탐색을 사용한다.
    let left = 1;
    let right = 200000000;

    while(left <= right) {
        const mid = (left + right) / 2 >> 0;

        let count = 0;
        for(let i = 0; i < stones.length; i++) {
            if(stones[i] - mid <= 0) count++;
            else count = 0;

            if(count === k) break;
        }

        if(count === k) right = mid - 1;
        else left = mid + 1;
    }

    return left;
}

thinkanddoit

2022.11.27 14:00

(정답주의) JS 풀이 공유 및 왜 이진탐색 문제인가?

작성중인 코드―solution.js

0 개의 답변

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.