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

아마 카테고리가 이분탐색이 아니었다면 전혀 생각하지 못했을거다.
답으로 구해야 하는 최댓값을 중간값으로 설정해 이분탐색 했다.

[ 풀이 ]

1. 0과 마지막 지점인 distance(25)를 가지고 가운데 값인 12로 답을 정하고 시작한다.

2. 문제의 답이 12라면 바위를 n개 제거했을 때 최소 거리가 12인 것이 있어야 한다.

3. 처음 위치를 0으로 두고 다음 바위까지의 거리가 mid(12) 보다 작으면 제거하고 아니면 그 바위 위치로 이동

   0 에서 2 까지의 거리 2 < 12 : 제거
   0 에서 11 까지의 거리 11 < 12: 제거
   0 에서 14 까지의 거리 14 > 12: 살려두기 and 14로 이동
   14 에서 17 까지의 거리 3 < 12: 제거
   14 에서 21 까지의 거리 7 < 12: 제거
   14 에서 25 까지의 거리 11 < 12: 제거

4. 제거한 바위가 n보다 많으므로 기준값을 줄인다.

   right = mid

5. 제거한 바위가 n보다 작거나 같으면

   left=mid+1

[ 문제 풀이 code ]

def solution(distance, rocks, n):
    answer = 0
    left,right=0,distance
    rocks.sort()
    
    while left<right:
        mid=(left+right)//2
        del_s=0 #제거 돌
        now_s=0 #현재 돌 위치
        for i in rocks:
            if i-now_s<mid:
                del_s+=1
            else:
                now_s=i
            if del_s>n:
                break
        if del_s>n:
            right=mid
        else:
            left=mid+1
            answer=mid
    
    return answer

📕 문제 확인

출처: 프로그래머스
링크: https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3