책너두 - 알고리즘 챌린지[6/20]

오늘의 문제 : 어두운 굴다리

어제와 같은 이분탐색 문제였다.

시간복잡도를 더 낮추고 싶은데 방법이 뭐가 있을지 궁금하다. 다른 분들 풀이가 많이 올라오면 확인해봐야겠다.

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
lamps = list(map(int, sys.stdin.readline().split()))

start = lamps[0]
end = n
ans = n+1

while start <= end :
    mid = (start+end)//2
    low_flag = False
    if lamps[-1] + mid < n :
        low_flag = True
    else :
        for i in range(m-1) :
            now_lamp = lamps[i]
            next_lamp = lamps[i+1]

            if now_lamp + mid < next_lamp - mid :
                low_flag = True
                break
    
    if low_flag == True :
        start = mid + 1
    else :
        end = mid - 1
        ans = min(ans, mid)

print(ans)