[프로그래머스💯] 코딩테스트 연습 > 이분탐색 > 징검다리

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    answer = 0
    l, r = 0, distance
    while l <= r:
        # print("l, r =>", l, r)
        prevRock, removeRock = 0, 0,
        cand = float('inf')
        minDistance = int((l+r)/2)
        for i in range(len(rocks)):
            if minDistance > rocks[i] - prevRock:
                removeRock += 1
                # print("removeRock")
            else:
                cand = min(cand, rocks[i] - prevRock)
                prevRock = rocks[i]
        if removeRock <= n:
            l = minDistance+1
            answer = cand
        elif removeRock > n:
            r = minDistance-1
    return answer

 

풀이)

처음 겪는사람에겐 너무나도 어려울 수 있는 이분탐색 문제입니다..

하지만 한 번만 이해하고 나면 나중에 나오는 문제들에는 큰 어려움 없이 수월해 질 수 있습니다! 화이팅!

 

키 포인트

보통 문제를 처음 접하면 , 돌을 없애보면서(돌을 없애는 루프를돌린다) 언제 거리가 최소가 나올지를 생각하죠.

 

하지만 그러면 엄청 오래걸립니다!!!! (코드 짜보면 시간초과 뜰 것입니다.)

 

=> 거리의 최솟값을 조절해가면서 그때 돌을 몇개빼야 하는지를 검사합니다!

 

우리가 구하고자 하는 것 : 거리의 최솟값의 최대값

돌을 더 많이뺴게 된다 => 거리의 최솟값을 줄여야한다.

돌을 더 적게 빼도 된다 => 거리의 최솟값을 늘려본다.

 

이 로직을 생각하시면서

minDistance를 이분 탐색을 이용해 조절해줍니다.

 

* 이와 매우 유사한 문제가 2019 카카오 개발자 겨울 인턴십 문제에 나왔습니다! (참고하시면 좋을 것 같습니다.)

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

프로그래머스

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges