징검다리
개요
- 이번 포스팅은 파이썬 코딩테스트 연습문제 풀이입니다.
Programmers에 공개된 예제이며 링크는 아래와 같습니다.
코드
def solution(distance, rocks, n):
rocks = sorted(rocks)
lo = 0
hi = distance
answer = 0
while lo <= hi:
mi = int((lo + hi) / 2)
prev = 0
cnt = 0
for rock in rocks:
if mi > (rock - prev):
cnt += 1
else:
prev = rock
if mi > (distance - prev):
cnt += 1
if cnt > n:
hi = mi - 1
else:
lo = mi + 1
answer = mi
return answer
마치며
이번 포스팅은 Programmers에 존재하는 파이썬 코딩테스트 이분탐색 예제 중 레벨 4에 해당하는 문제입니다.