[Programmers] 징검다리

문제

출발 지점부터 도착 지점까지 놓인 바위 중 n개를 제거해 각 지점 사이 거리 최솟값 중 가장 큰 값을 구하는 문제. 도착 지점까지의 거리 (distance)는 1부터 10억. 바위 개수는 5만 개로 조건이 주어진다.

 

각 바위가 [2, 14, 11, 21, 17] 로 주어지고 n이 2라고 가정하면, [2, 14]를 제거했을 때 각 바위 사이 거리는 [11, 6, 4, 4]가 되고, 거리의 최솟값은 4가 된다. 다른 값과 비교했을 때 이 값이 제일 크므로 답은 4.

 

회고

이게 왜 이분 탐색인가..? 생각이 가장 먼저 들었고, 어떻게 접근해야 문제를 풀 수 있을지 한참 고민. 도착 지점까지의 거리가 10억이라는 부분에서 힌트를 얻었어야 하는 문제였다. 애초에 바위 개수가 5만 개인 상황에서 n개를 전부 빼보는 조합을 쓴다면 무조건 시간 초과가 발생하는 상황이고, 이 때 탐색 대상을 '바위를 n개 제거했을 때 최소 거리가 얼마인지'가 아닌 '최소 거리가 x일 때 제거해야 하는 바위 수가 n개 이하인지'로 접근해야 풀 수 있던 문제.

 

이러한 이분 탐색 문제는 가장 까다로운 부분이 조건 설정으로 보이는데... 개인적으로 난항을 겪었던 부분을 몇 가지 꼽자면 다음과 같다.

• 오랜만에 풀다 보니 high와 low 값을 갱신할 때 각각 mid-1, mid+1로 설정해줘야 값이 유의미하게 변한다는 점을 까먹었고...
• while 문 탈출 조건 부분에서 거듭 헷갈린 점 (등호를 붙일지 말지)
• 또한 이 문제의 경우 answer를 계속해서 값을 갱신해줘야 했는데, cnt가 n보다 작을 때마다 잡아주면서 최대값을 구했어야 했다.

이분 탐색은 계속 풀어보면서 감을 익히는 게 중요하다. 아자아자.

---

def solution(distance, rocks, n):
    answer = 0    
    low, high = 0, distance
    rocks.sort()

    while low <= high:
        mid = (low + high)//2
        curr, cnt = 0, 0

        for rock in rocks:
            if rock - curr >= mid:
                curr = rock
                continue
            cnt += 1

        if distance - curr < mid:
            cnt += 1

        if cnt > n:
            high = mid-1
        elif cnt <= n:
            answer = mid
            low = mid+1

    return answer