프로그래머스, 징검다리건너기, 64062

[유형]

이분탐색

 

[문제링크]

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

 

[요약]

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

[문제풀이]

mid : 징검다리를 건널 수 있는 최대 인원

cnt : 건너지 못하는 연속된 돌의 개수

stone <= mid : mid가 stone을 다 건너지 못하는 경우, 건너지 못하는 연속된 돌의 개수를 증가시킨다.

stone > mid : mid가 stone을 모두 건널 수 있으므로, 건너지 못하는 연속된 돌의 개수를 0으로 초기화한다.

cnt >= k :징검다리를 건널 수 있는 최대 인원을 줄여야 한다는 의미이고

cnt < k : 징검다리를 건널 수 있는 최대 인원을 늘려야 한다는 의미이다.

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