[프로그래머스] 징검다리

[프로그래머스] 징검다리

문제

https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3

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

 

나는 이분탐색문제가 나오면 조합으로 풀려는 아이디어가 가장 먼저 떠오른다.

실제로 테스트케이스의 범위가 제한적이라면 분명 조합으로 더 쉽게 풀수 있을것이다. 하지만 이분탐색의 문제는 범위가 굉장히 크고, 절대 조합으로 풀수없게 테스트케이스를 구성해놓는다.

이런점을 간과하고 문제를 풀때 조합으로 시도하면서 시간을 날리곤 하는데 이 문제도 조합생각하다가 시간을 날렸다...

하지만 과연 누가 이 문제를 "이분탐색으로 풀자" 라는 생각을 떠올릴까,, ㅠ?

보통 문제를 풀기위해 문제분석을 하고 이분탐색이라는 결론이 내려지면 20~30분 정도면 푸는데, 이 문제는 이분탐색 결론을 내렸는데도 문제를 풀지 못해 결국 다른 블로그를 참고했다.

이분탐색의 어려운 문제를 풀고싶다면 이 문제가 적격인거같다.

코드 설명

이분탐색 문제를 풀때 가장 중요한건 기준 을 잡는건데, 여기서 기준은 각 바위사이의 거리의 최소값이다.

알고리즘 순서

1. left = 0, right = distance 의 중간값(mid) 기준으로 한다. (여기서 mid값은 거리의 최소값)
2. mid를 기준으로 바위사이의 거리가 mid보다 작으면 제거, 크거나 같으면 minV과 비교하여 갱신
3. 제거된 바위가 n보다 클경우 mid를 줄이기 위해 right = mid-1 갱신
4. 제거된 바위가 n이랑 같거나 작을경우 mid를 늘리기 위해 left= mid + 1 갱신

최근에 풀었던 문제중 수학적 관점에서 가장 어려웠다..

def solution(distance, rocks, n):
    ans = 0
    rocks.sort()
    left = 0
    right = distance
    while left <= right:
        mid = (left + right) // 2
        pre = 0     # 출발지점
        minV = float('inf')
        removed_rock = 0
        for rock in rocks:
            if mid > rock - pre:
                removed_rock += 1
            else:
                minV = min(minV, rock - pre)
                pre = rock
        if removed_rock > n:
            right = mid - 1
        else:
            left = mid + 1
            ans = minV
    return ans