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

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

---

입출력

입/출력

---

풀이

def solution(distance, rocks, n):
    answer = 0
    rocks.sort() # 이분탐색을 위한 정렬
    left,right = 1,distance
    
    while left <= right :
        mid = left + (right - left) // 2
        pre_rock = 0 # 현재 위치를 담을 변수
        num_rock = 0 # 바위 개수 카운트 변수
        min_rock = 1000000001 # 최솟값
        
        for rock in rocks:
            rock_calc = rock - pre_rock # 바위끼리 거리를 계산
            if rock_calc < mid: # 중간값보다 작으면
                num_rock += 1 #제거 바위 + 1
            else: # 중간값보다 크거나 같으면 제거 못하니 최소값을 갱신하고 현재 위치를 변경
                min_rock = min(min_rock, rock_calc)
                pre_rock = rock
                
        if num_rock > n: # 바위를 너무 많이 제거했으니 mid 값을 축소
            right = mid - 1
        else: # 제거를 너무 적게 했거나 딱 맞으면 최솟값을 answer를 갱신하고 범위 축소
            answer = min_rock
            left = mid + 1
    return answer

결과

---

문제 풀이

1. 제한 사항에서 distance 값이 매우 크기 때문에 선형 탐색으로는 원하는 값을 도출할 수 없다고 생각했다.
2. 그렇다면 이분 탐색으로 범위를 줄여 나가면서 풀어야 한다고 결론지었고 이분 탐색으로 접근했다.
3. 문제를 이해를 제대로 못해서 바위와의 거리 차를 통해서 문제를 풀어야 하는 것을 깨닫지 못했다.
4. 이분 탐색은 정렬을 해주어야 하는데 정렬을 하지 않고 문제를 풀어나가니 계속 원하는 답이 나오지 못했다.
5. left가 right보다 크거나 같아질때까지 반복문을 수행하면서 내부의 로직을 수행한다.
6. 바위 사이를 계산하면서 mid값 보다 작으면 바위를 제거하고 크면 최솟값을 갱신하며 현재 바위의 위치를 갱신한다.
7. 바위의 개수가 제거할 바위의 개수를 넘어산다면 mid값을 새로 경신하고 
8. 바위의 개수가 같거나 적다면 answer를 갱신하고 mid 값을 새로 경신한다.