[이분 탐색] 징검다리 건너기 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 문제 조건
  • stones 배열의 크기는 1 이상 200,000 이하입니다.
  • stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• 처음에는 한번에 건널 뛸 수 있는 k 만큼 돌을 묶어서 그 안의 범위 중 최댓값을 찾고 또 그 최댓값 중 가장 작은 값을 결과로 출력함
• 하지만 이럴 경우 중간 중간 묶었을 때 발생하는 공백들로 인해 묶음의 범위가 또 달라짐
• 공백들을 생각하면 묶어서 푸는 문제가 아니라 판단.
• 원소의 값이 2억 이하인 것에서부터 원소의 최댓값을 end로 잡는 이분 탐색을 통해 각 자리 별로 mid 값을 비교하면서
• mid보다 작으면 cnt+1, 크다면 0으로 초기화 해줌
• 이때 cnt가 k 이상이 되면 그 mid값은 너무 큰 것이므로 재탐색 해줘야함(크니까 end를 작은 값인 mid-1로 잡아주기)
• k가 더 크다면 mid 값이 작은 것이므로 start를 mid+1로 잡기
• while문 탈출 조건인 start<=end를 통해 최종 통과한 start가 결과값임을 알 수 있음
•  

소스 코드

def solution(s, k):
    answer = 0
    start = 0
    end = max(s)
    while(start<=end):
        mid = (start+end)//2
        cnt = 0
        for temp in s:
            if temp<=mid:
                cnt+=1
            else:
                cnt=0
            if cnt>=k:    
                end=mid-1    
                break
        
        if cnt<k:
            start=mid+1
            
        

    return start



print(solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1],3))