[프로그래머스] 징검다리 건너기 (Python)

📕 문제

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

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

 

💡 풀이법

: 배열의 크기가 20만이고 원소들의 값들이 2000만이 최대였기 때문에 바로 logN의 시간복잡도를 가지는 이분탐색을 생각했다.

 

1. 구하고자 하는 최대 사람수를 1부터 배열의 값 중 가장 큰 값 사이에서 구해야한다.

2. 값을 최소와 최대값의 반으로 설정하고 돌들을 돌면서 그만큼의 사람이 갈 수 있는지 구한다.

3. 갈 수 없으면 값을 줄이고(최소값과 현재 사람수의 반), 갈 수 있다면 값을 늘린다(현재 사람수와 최대값의 반).

def solution(stones, k):
    answer = 0
    start, end = 1, max(stones)
    while start <= end:
        middle = (start + end)//2

        max_cnt = 0
        cnt = 0
        flag = False
        for stone in stones:
            if stone - middle <= 0:
                if flag:
                    cnt += 1
                else:
                    max_cnt = max(max_cnt, cnt)
                    cnt = 1
                    flag = True
            else:
                flag = False
                         
        max_cnt = max(max_cnt, cnt)

        if max_cnt >= k:
            end = middle - 1
            answer = middle
        else:
            start = middle + 1
    
    return answer