[python] 43236 징검다리

1. 문제

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

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

2. 접근 방법

전 문제(입국심사)를 풀면서 거리를 기준으로 이분탐색을 하면 되겠다는 생각을 했습니다.

 

그래서 거리를 기준으로 제거되는 바위의 갯수를 세고, 해당 바위의 갯수가 n개보다 많을 때에는 기준 거리를 줄이고, n개보다 적을 때에는 기준거리를 늘리고, n개일 때 return하게 짰습니다.

 

근데 요러케 하면 ^^ 왜인지는 모르겠지만 엄청나게 틀리더라구여

 

그래서 질문하기를 봤더니 다들 문제에 오류가 있는 것 같다며 n개가 아닌 n개 이하에 대해 고려하도록 코드를 수정하라고 되어 있어서 n개보다 적을 때에 answer를 갱신(answer와 mid 중 큰 값으로 갱신)하도록 수정했습니다.

3. 코드

Python

def solution(distance, rocks, n):
    answer = 0

    left = 0
    right = distance

    rocks.sort()

    def check(val):
        start = 0
        delete_cnt = 0
        for i in range(len(rocks)):
            rock = rocks[i]
            if abs(start - rock) < val:
                delete_cnt += 1
            elif abs(start - rock) >= val:
                start = rock
        return delete_cnt

    while left <= right:
        mid = (left + right) // 2

        delete_cnt = check(mid)
        if delete_cnt > n:
            right = mid - 1
        else:
            left = mid + 1
            answer = max(answer, mid)
    return answer

4. 마치며

이분탐색을 몇 개 더 풀어봐야겠슴다