[프로그래머스] 징검다리 건너기 python

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

프로그래머스

2019 카카오 개발자 겨울 인턴십 마지막 5번 문제이다.

인턴십 문제라 그런지 생각보다는(?) 평이한 이분탐색 문제였다.

 

문제해결 

길이가 20만인 stones를 순차탐색을 하지만 값이 최대 2억인 값을 기준으로 이분탐색을 진행한다.
O(N*logN) 시간복잡도를 띄기에 시간복잡도 내에 통과가능하다.
left = 1, right = max(stones)로 잡고 k를 기준으로 left,right를 나누어
stones에 대해 이분탐색을 진행하면 징검다리를 건널 수 있는 최대인원수를 구할 수 있다.