def solution(stones, k):
lo = 1
hi = max(stones)
while lo < hi:
mid = (lo + hi) // 2 # mid = 징검다리를 건너는 친구 수
gap = 0 # 0의 개수
for i in range(len(stones)):
if stones[i] - mid <= 0: # 반복문으로 징검다리를 -1 하지 않고
# 친구수(mid)만큼 한번에 빼버린다.
gap += 1
else:
gap = 0 # 0이 연속적인 경우에만 고려해야하기 때문에 0으로 초기화
if gap >= k:
break
if gap >= k:
hi = mid
else:
lo = mid + 1 # lower bound
return lo
이분탐색을 통해 답을 구한다.
단, 미리 답이 정해져있다고 간주하여 풀어야한다.
-> 즉, mid값이 답이라고 정해둔 뒤, 이후에 답(mid) 검증하는 순서