Programmers / 3단계 / 징검다리 건너기 / python / 2019 카카오 개발자 겨울 인턴십

 

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

 

 

코드

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

 

- 순차탐색으로는 효율성을 만족하기 어려우므로 이진탐색으로 답을 구해야 한다.

- s는 1, e는 디딤돌의 최댓값, mid는 (s + e) //2로 설정하고, 디딤돌을 반복문을 돌려 mid값을 빼고 건널 수 있는지 확인한다. 

- 건널 수 없으면 cnt += 1 / 건널 수 있으면 cnt = 0으로 초기화

- cnt가 k보다 크면 디딤돌을 mid명 만큼 건널 수 없기 때문에 e를 mid-1로 갱신한다.

- mid명이 모든 디딤돌을 건널 수 있는 경우 s를 mid+1로 갱신한다.