입국심사와 매우 비슷한 문제다. 혹시 이문제를 모른다면 무조건 보고와야한다.
def check(stones, k, people) :
sinked = 0
for stone in stones :
sinked = sinked + 1 if stone < people else 0
if sinked == k : return False
return True
def solution(stones, k):
min_ = min(stones)
max_ = max(stones)
if min_ == max_ : return min_
while min_ < max_:
estimate = (min_ + max_) // 2
if check(stones, k, estimate) :
min_ = estimate + 1
else:
max_ = estimate
return min_ - 1
징검다리를 건널 추정 인원
만약 k = 3일 때, 이 돌다리를 1명이 건넌다면 어떻게 될까?
1 명은 모두 건널 수 있는걸 확인했다. 2명은 어떨까?
2명도 씹가능이다. 그럼 3명은?
3이하의 돌은 전부 무너져버린다. 이때는 못넌거는것을 확인할 수 있다.
오 3트만에 답을 찾아버렸다. 그런데 돌다리갯수는 최대 20만개고 돌다리 원소 최대값은 2억이다. 돌다리 20만개에 모든 원소가 2억이라는 최악의 경우엔 200000000 x 200000 번의 계산을 해야하는데, 이런식으로 순차적으로 계산할바엔 건널 수 있는 인원의 최대/최소값을 정해놓고 BinarySearch를 해버리는게 어떨까
다리를 건널 추정인원
n이하의 돌을 순차적으로 깨나가면서 돌과 돌사이의 거리가k가되면 다리를 못건너는 것으로 판단하고 다시BinarySearch진행한다.
이게 핵심 알고리즘이다.
돌다리 체크
def check(stones, k, people) :
sinked = 0
for stone in stones :
'''
사람 수보다 적은 돌은 터트리고 터트린 돌의 갯수를 늘려주고, 돌이 사람 수보다 많으면 다시 터트린 돌의 수를 리셋시킨다.
'''
sinked = sinked + 1 if stone < people else 0
if sinked == k : return False # 터트린 돌이 `k`개가되면 못건너니 False리턴
return True
BinarySearch
def solution(stones, k):
min_ = min(stones) # 추정인원 최소값
max_ = max(stones) # 추정인원 최대값
if min_ == max_ : return min_ # 돌다리 최대, 최소값 같은 경우
while min_ < max_:
estimate = (min_ + max_) // 2
if check(stones, k, estimate) : # 건널 수 있으면 추정인원 최소값을 늘려준다.
min_ = estimate + 1
else: # 못건너면 추정인원 최대값을 줄여준다.
max_ = estimate
return min_ - 1
사실 이부분이 제일 어렵다.
check함수는 건널 수 있으면 True를 반환하고 min_값을 갱신해준다, 못건너면 False를 반환하고 max_값을 갱신해 준다. 하지만 이 BinarySearch의 함정은 현재 estimate 인원이 건널 수 있는 최적값일 때도 estimate+1을 해주어서 최종 답인 min_이 구하고자하는 답보다 1이 큰 상태가된다.
최적답이 한번 구해지는 순간
최적답+1 <= 추정인원 <= 최대값이 사이에서 BinarySearch를 진행하기 때문에 최종 결과는최적답+1이 나와버린다.
그래서 최종 답은 min_ - 1이됨.