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

문제

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

풀이

1. 제한사항 보기

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하이다. (0 <= distance <= 10억)
• 바위는 1개 이상 50,000개 이하이다. (1 <= 바위 <= 5만)
• n 은 1 이상 바위의 개수 이하이다. ( 1 <= n <= 바위)

2. 바위를 n개 만큼 조합해서 하면 시간 초과로 인해 당연히 안되고 distance의 범위도 10억이기 떄문에 완전 탐색으로는 풀 수 없다.

3. 따라서 이진 트리 알고리즘을 통해 풀도록 한다.

4. 임의로 중간 값(mid)를 목표로 하는 거리의 최솟값으로 지정한다.

5. 만약 거리의 최솟값을 목표로 하고 바위는 거리의 최솟값보다 좁은 바위는 깨버리고 깨버린 개수를 카운팅한다.

6. 깨버린 갯수가 n보다 많으면 깨야할 것들 많으므로 목표로 하는 거리의 최솟값는 좁혀주고 n보다 적거나 같게 깰 수 있다고  목표 범위를 높인다.

7. 반복해서 left와 right와 같다면 반복문에서 나와주고 결과값을 리턴한다.

8. left가 결과값인 이유는 이분탐색시 left가 조건을 만족하는 최대의 답이고 right가 조건을 불만족 하는 최소의 답이기 때문이다.

코드

def break_rocks(rocks, offset):
    break_count = 0
    prev_rock = 0

    for i in range(1, len(rocks)):
        if rocks[i] - prev_rock < offset:
            break_count += 1
        else:
            prev_rock = rocks[i]

    return break_count


def solution(distance, rocks, n):
    rocks.sort()
    left, right = 1, distance

    while left + 1 < right:
        mid = (left + right) // 2
        res = break_rocks([0]+rocks, mid)

        if res > n:
            right = mid
        else:
            left = mid

    return left