[Level 3] 징검다리 건너기

https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

---

접근

최대로 건널 수 있는 사람부터 한 명까지 탐색을 한다. 그리고 건널 수 있는 사람의 명수를 stones에 있는 각각의 숫자와 빼준다. 이때 0이하인 숫자가 K개 이하라면 해당 숫자가 최대로 건널 수 있는 사람의 명 수가 된다. 

하지만 stones에 있는 원소는 최대 200,000,000의 수를 갖기 때문에 효율성 테스트에서 통과하지 못할 것이다. 따라서 선형적으로 탐색하는 것이 아니라 이진탐색을 활용한다. 

이진 탐색으로 건널 수 있는 사람의 명수를 찾는다.

 

구현

- left는 1, right는 stones의 최대값을 넣는다.

- 이제 left와 right를 활용하여 건널 수 있는 사람의 수인 mid를 구한다.

- mid를 stones의 원소와 빼서 0이하일 때 카운트하고 count가 K 이상일 때 종료한다.

- left와 right를 갱신시키기 위해서는

- count가 k보다 작을 때는 사람의 수를 더 키워도 되는 것이기 때문에 left를 증가시키고

- count가 k 이상일 때는 사람의 수를 줄여야하기 때문에 right를 감소시킨다.

- 이진 탐색이 종료되었을 때는 left를 해로 갖는다.

def solution(stones, k):
    left = 1
    right = max(stones)
    while left <= right:
        mid = (left + right) // 2
        count = 0
        for stone in stones:
            if stone - mid <= 0:
                count += 1
            else:
                count = 0
            if count >= k:
                break

        if count < k:
            left = mid + 1
        else:
            right = mid + 1

    return left