프로그래머스 레벨 3 징검다리 건너기 (2019 카카오)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/64062

첫번째 코드 (효율성 테스트 실패)

def solution(stones, k):
    
    max_val_list=[]
    #연속된 0의 갯수가 k개면 불가능 해지는거네
    
    for i in range(len(stones)-k):
        max_val_list.append(max(stones[i:i+k]))
    
    return min(max_val_list)

아무리 해도 효율성에서 에러가 나길래 주변 똑똑한 동기에게 부탁했다
해답은 이진탐색이었음 ㅅㅂ 이진탐색 문제를 평소에 안풀긴 했지만 진짜 이진탐색은 생각치도 못한 풀이.

동기가 힌트로 제시해준 사진.

동기는 디딤돌이 가라앉는것이 아닌 수면이 올라오는 개념으로 접근했다.

그렇다면 수면의 범위는 0~200,000,000 이 되고, 이 사이 숫자들 중 모든 애들이 건널 수 있는 최대 높이를 계산하면됨.
0~200,000,000의 범위를 이진탐색으로 줄여나가 주면서, 그때 모든 애들이 건널수 있는지 (범위 1~200,000)를 계산해주면된다.

정답코드

def solution(stones, k):
    answer=0
    maxval=max(stones)
    minval=min(stones)
    while minval<=maxval:
        midval=(maxval+minval)//2
        count=0
        for i in range(len(stones)):
            if stones[i]<midval:
                count+=1
                if count==k:
                    break
            else:
                count=0
        if count>=k:
            maxval=midval-1
        else:
            answer=midval
            minval=midval+1
    return answer

처음에 정확성 테스트가 반타작이 나오길래 왜그런가 했는데
while문의 조건을 잘못 설정해줬음
while minval<=maxval: 이거를 while minval<maxval: 로 해주어서 에러가 난거
minval이 maxval과 같은 값이 되는 순간이 답이다.
이진탐색은 추후 공부 더 하기로

이렇게 했을때 시간복잡도200000*log200000000