[코테 - py] 징검다리

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

프로그래머스

오늘 문제는 이분탐색 문제였다.

해당 문제는 풀이를 참고했다!

 

이분탐색 문제는 연습을 더해야겠다고 느꼈다.

"""
입력의 사이즈가 너무 커서, 완전탐색이 아니라고 판단하면! 이분탐색을 시도해보자!!
"""
def solution(distance, rocks, n):
    left = 1
    right = distance
    
    rocks = sorted(rocks)
    rocks.append(distance)
    
    while left <= right:
        mid = (left+right) //2
        remove = 0
        prev = 0
        
        for v in rocks:
            dist = v - prev
            if dist < mid:
                remove += 1
                if remove > n:
                    break
                
            else:
                prev = v
                
        if remove > n:
            right = mid - 1
        else:
            answer = mid
            left = mid + 1
    return answer

 

아래는 하나씩 생각하면서 정리한 풀이다.

복습이 필요한 문제!