[프로그래머스] 징검다리 건너기 / 파이썬 / python / 이진탐색

 

💡 solutions  

💬 순차탐색으로는 효율성을 만족하기 어렵기 때문에 이진탐색으로 다리를 건널 수 있는 최대 인원을 찾아야 한다.

💬 start는 1, end는 max(stones) 디딤돌의 최댓값으로, mid는 (start+end)//2로 설정

💬 디딤돌을 앞에서부터 하나씩 꺼내와 mid값을 빼고 건널 수 있는지 없는지 확인

      -> 건널 수 없는 경우 cnt += 1 / 건널 수 있는 경우 cnt = 0으로 초기화

💬 cnt값이 k개 이상이면 디딤돌을 mid명 만큼 건널 수 없기 때문에 반복문 break -> end를 mid-1 로 갱신

💬 반복문이 온전히 종료된 경우, 즉  mid명이 모든 디딤돌을 건널 수 있는 경우 -> start를 mid +1 로 갱신

 

👨‍💻 code  

def solution(stones, k):
    start = 1
    end = max(stones)
    mid = (start + end) // 2

    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        for stone in stones:
            if (stone - mid) <= 0:
                cnt += 1
                if cnt >= k:
                    end = mid - 1
                    break
            else:
                cnt = 0
        else:
            start = mid + 1
    return start

 

 

📌 problem  

코딩테스트 연습 - 징검다리 건너기