[알고리즘][2][X][문제 오류] 징검다리

문제 설명
출발지점부터 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 이상 바위의 개수 이하입니다.
입출력 예
distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4
입출력 예 설명
문제에 나온 예와 같습니다.

출처

※ 공지 - 2020년 2월 17일 테스트케이스가 추가되었습니다.
※ 공지 - 2023년 5월 15일 테스트케이스가 추가되었습니다. 기존에 제출한 코드가 통과하지 못할 수도 있습니다.

나의 풀이

- 우선 문제에 오류가 있다. 이 문제는 n개 이하로 제거된다고 가정해야 정답이 된다.

- 그런데 그 이유가 n개가 딱 맞춰지지 않아서라고 할 수도 있는데 그렇게 되면 제거할 수 있는 돌의 개수가 n개 이하가 아닌 n-1개 미만으로 제시되어야 했다. 왜냐하면 돌을 전부 지우게 되면 최솟값도 날라가 버리기 때문이다. 만약 answer에 n개 미만일 때가 저장되어 있고 n-1개 미만을 지울 수 있다고 가정하면 최솟값만 건드리지 않고 나머지를 제거하면 된다. 그러나 그렇지 않으면 돌을 다 지우게 되면 안되고 또한 돌 사이일 때가 최소일 수도 있으므로 n-1개를 지워도 안되는 경우가 있을 수 있다. 이런 경우들을 전부 고려하지 못하기 때문에 이 풀이를 의도했던 문제에는 오류가 있다고 볼 수 있다.

 

맞는 풀이

import math

def solution(distance, rocks, n):
    # 최댓값과 최솟값을 구해야하므로 그리디, DP, 탐색
    # 바위가 50,000개 있고 n을 중간으로만 잡아도 경우의 수가 커진다 따라서 탐색 X
    # 중간 결과를 저장할 방법도 없으니 DP X
    # 항상 최선의 선택을 할 수 없으므로 그리디 X
    # 그럼 이분탐색
    
    answer = distance
    
    left = 0
    right = distance
    rocks.sort()
    rocks.append(distance)
    while left <= right:
        middle = (left + right) // 2
        min_distance = math.inf
        std_rock = 0
        del_rocks = 0
        for rock in rocks:
            gap = rock - std_rock
            if gap < middle:
                del_rocks += 1
            else:
                std_rock = rock
                min_distance = min(min_distance, gap)
                
            
        
        if del_rocks > n:
            right = middle - 1
        else:
        	answer = min_distance
            left = middle + 1
    
    return answer

틀린 풀이

- 둘의 차이는 del_rocks < n일 때의 값을 answer에 넣어주냐 아니냐의 차이다.

import math

def solution(distance, rocks, n):
    # 최댓값과 최솟값을 구해야하므로 그리디, DP, 탐색
    # 바위가 50,000개 있고 n을 중간으로만 잡아도 경우의 수가 커진다 따라서 탐색 X
    # 중간 결과를 저장할 방법도 없으니 DP X
    # 항상 최선의 선택을 할 수 없으므로 그리디 X
    # 그럼 이분탐색
    
    answer = distance
    
    left = 0
    right = distance
    rocks.sort()
    rocks.append(distance)
    while left <= right:
        middle = (left + right) // 2
        min_distance = math.inf
        std_rock = 0
        del_rocks = 0
        for rock in rocks:
            gap = rock - std_rock
            if gap < middle:
                del_rocks += 1
            else:
                std_rock = rock
                min_distance = min(min_distance, gap)
                
            
        
        if del_rocks > n:
            right = middle - 1
        elif del_rocks == n:
            answer = min_distance
            left = middle + 1
        else:
            left = middle + 1
    
    return answer