[프로그래머스] Lv.3 징검다리 건너기 [Python, 파이썬] KAKAO

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/64062
• 🔑 이진 탐색
  • 처음 풀이는 k 크기의 슬라이딩 윈도우로 각 윈도우의 최댓값을 저장하고 그중 최솟값을 반환했다.
  • 정확성은 다 맞지만 효율성이 집에 가라고 했다.
  • 그래서 이진 탐색으로 풀이를 했다.
  • mid 명이 건너면서 연속으로 k개가 부서졌으면 사람 수를 줄였다.
  • 무사히 건널 수 있으면 사람 수를 늘려서 최대로 몇 명이 건널 수 있는지를 구했다.

 

def solution(stones, k):

    l = 1
    r = 200_000_000
    
    while l <= r:
        mid = (l + r) // 2          # 몇 명이 건너볼까?
        cnt = 0                     # 부서진 돌 개수 카운트
        
        for stone in stones:
            if stone - mid <= 0:    # 부서졌으면
                cnt += 1            # 개수 올린다.
            else:                   # 안 부서졌으면
                cnt = 0             # 개수 초기화 (연속으로 k 개가 부서져야 못 건너니까)
            if cnt >= k:            # 연속으로 k 개가 부서졌으면 못 건너니까
                r = mid - 1         # 사람 수를 줄이고
                break               # 멈추자
                
        else:                       # 건널 수 있으면  (break 안 걸렸으면)
            l = mid + 1             # 사람 수를 늘려보자 (최대를 구해야 하므로) 
    
    return l