[프로그래머스][python]징검다리 건너기

문제

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

소스코드

    def solution(stones, k):
        l,r = 1,200000000
        answer = 0
        
        while l <= r:
            mid = (l+r)//2
            tmp_cnt = 0
            for s in stones:
                if s - mid <= 0 :
                    tmp_cnt +=1
                else:
                    tmp_cnt = 0
                if tmp_cnt >= k:
                    break
            if tmp_cnt >= k:
                r = mid -1
            else:
                l = mid + 1

        answer = l
        return answer

설명

각 돌에 1씩 빼서 K가 나오면 중단하는 방식으로 풀 수 있다. 하지만 이렇게 하면 효율성을 맞출 수 없다.

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

(예전에 풀었던 문제 참고)

 

효율성을 맞추기 위해 이분탐색으로 푼다.

• target = 건널 수 있는 사람 수
• l, r = 문제에서 나온 최소 돌의 값과 최대 돌의 값 ( 돌의 값이 결국 건널 수 있는 사람 수이다.)

최댓값을 구하기 때문에 우리가 구하고자 하는 mid + 1 인 l 값이 정답이다.

 

범위를 체크 하는 방식은 아래와 같다.

1. 너무 조금 건넌 경우 (tmp _ cnt가 k 보다 작은 경우)

l = mid + 1 해서 범위를 늘린다.

 

2. 너무 많이 건넜거나 정답과 같은 경우 (tmp_cnt가 k보다 크거나 같은 경우)

r = mid -1 해서 범위를 줄인다.