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

문제

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

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

풀이

징검다리를 건널 수 있는 인원 ans를 이분탐색으로 찾는다.

1. N명이 징검다리를 건널 수 있는가?

• 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있으므로,
• 다딤돌의 숫자와 인원수 N을 비교한다.
• 건널 수 없는 디딤돌이 연속으로 K개 이상 있으면, N명이 짐검다리를 건널 수 없다.

2. 징검다리를 건널 수 있는 인원 찾기

• 시작값과 끝값을 정한다.
  • 0 ~ max(stones)
• 중간값 mid명이 징검다리를 건널 수 있으면, 짐검다리를 건너는 인원을 늘려본다.
  • start = mid +1
• 중간값 mid명이 징검다리를 건널 수 없으면, 짐검다리를 건너는 인원을 줄여본다.
  • end = end - 1

코드

def solution(stones, k):
    # N명이 징검다리를 건널 수 있는가?
    def available(n) : 
        skip = 0
        for value in stones : 
            if value < n : 
                skip += 1
                if skip >= k : return False
            else : skip = 0
        return True
    
    # 이분탐색
    s, e = 0, max(stones)
    ans = 0    
    while s<=e : 
        mid = (s+e)//2
        if available(mid) == True : 
            s = mid + 1
            ans = max(ans, mid)
        else : e = mid - 1
    
    return ans