1. 아이디어
효율성 테스트에서 틀리겠지만, 우선 단순하게 생각하자. 초기에 1명이 징검다리를 건너면 돌에 적힌 숫자는 1씩 차감된다. 그리고 2번째 사람이 징검다리 앞에 있다. 2번째 사람부터 징검다리를 건널 수 있는지 확인해야한다. 연속적으로 숫자 0이 적힌 돌의 개수가 k개이면 건널 수 없다. 건널 수 있는 조건이라면 2번째 사람을 건너게 하고, 돌에 적힌 숫자를 1씩 차감한다. 징검다리를 건너는 친구들의 수는 무제한이기 때문에, 연속적으로, 숫자 0이 적힌 돌의 개수가 k개가 될 때 까지 건널 것이다.
만약 k와 돌의 개수가 20만, 각 돌에 쓰여진 숫자가 2억이라고 하자. 2억명의 사람이 20만개의 돌을 건널 것이다. 사람이 들어올 때 마다 20만개의 돌을 건널 수 있는 지 확인해야하므로 2억 x 20만번의 연산을 거치게 된다. 따라서 효율성 테스트에서 오답을 받게된다.
돌을 건널 수 있는지 검사를 해야하기 때문에, 20만번의 연산을 그 아래로 줄 일 수 없다. 대신, 2억의 연산은 이분 탐색을 이용하여 줄일 수 있다. 돌에 적힌 숫자 n = n 번째 사람이 징검 다리를 건널 때라고하자. 제약조건에 따르면, 숫자에 적힌 돌의 최소 범위는 1이기 때문에 left = 1로 설정한다.(i.e. 최소 1사람은 징검다리를 건넌다.) right = 돌에 적힌 수 중 가장 큰 수로 설정한다.
이분 탐색에서 mid(left~right 범위 중 중간 값)를 얻는다. 그리고 각 돌에 적힌 숫자에서 mid를 빼고 1를 더한다. 1를 더하는 이유는 mid번째 사람은 아직 징검다리를 건너지 않았기 때문이다.(바로 윗 문장 참고) 만약 연산 결과가 음수이면, 음수 대신 0을 돌에 적는다.(음수가 나왔다는 것은 돌에 0인 적힌 이후, 사람들이 해당 돌을 밟지않고 건너뛰었다는 것을 의미).
각 돌에대해 연산을 완료했으면, 0이 k번 연속적으로 나타나는지 확인하면 된다. 만약 연속적으로 나타났으면, mid번째 이상 사람은 모두 건널 수 없다는 것을 의미하므로 right = mid - 1설정한다. 만약 건널 수 있으면, mid 값을 다른 변수에 저장하고, mid번째 이후의 사람이 건널 수 있는지 확인한다. 따라서 left = mid + 1로 설정한다.
이분탐색을 거치면서 조건을 만족하는 결과 중 최대 값을 구하면 된다.
2. 코드
def solution(stones, k):
answer = 0
left = 1
right = max(stones)
size = len(stones)
copy = [s for s in stones]
while left <= right:
mid = (left + right) // 2
for i in range(size):
x = stones[i] - mid + 1
stones[i] = x if x > 0 else 0
seq = 0
for i in range(size):
if stones[i] == 0: seq += 1
else: seq = 0
if seq == k: break
for i in range(size): stones[i] = copy[i]
if seq < k:
answer = max(answer, mid)
left = mid + 1
else: right = mid - 1
return answer