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

문제 설명 

출발지점부터 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

---

문제 풀이 

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 계속해서 찾아나가는 과정이 필요하므로 탐색으로 문제를 해결해야겠다고 생각했다. 

하지만 탐색해야 할 양이 매우 많으므로 이분 탐색으로 문제를 해결해하면 더 효율적인 코드를 작성할 수 있을 것 같았다. 

 

이분탐색은 배열이 정렬되어 있을 때만 탐색이 가능하므로, 먼저 rocks 배열을 오름차순으로 정렬해주었다. 

그런 다음, start와 end 값을 적절히 설정해주어야 하는데 

문제에서 구하고자 하는 값이 각 지점 사이의 거리의 최솟값 중 가장 큰 값이므로 

최솟값 중 가장 큰 값이 될 수 있는 가장 작은 수는 1이고 가장 큰 수는 distance 값인 25이다. 

따라서 start는 1, end는 25로 설정해주었다. 

 

Step 1 

start = 1, end = 25, mid = 13 일 때 

0

2

11

14

17

21

25

mid값인 13은 각 지점 사이의 거리의 최솟값중 가장 큰 값을 의미하므로 13보다 더 작은 수가 있어서는 안된다. 

따라서 previous 값을 설정해준 후 배열의 0번째 인덱스부터 각 지점 사이의 거리를 구해서 

만약 13보다 더 작은 수가 나온다면 그 지점의 값을 삭제해준다. 

만약 삭제되지 않았다면 previous값을 그 다음 지점의 값으로 이동시켜주어야 한다. 

여기서 삭제될 값은 n개를 초과하게 된다. 따라서 end의 값을 mid-1 로 설정하여 mid값을 줄여준다. 

Step 2 

start = 1, end = 12, mid = 6 일 때 

0

2

11

14

17

21

25

여기서 mid 보다 작은 값을 가지는 지점을 삭제하면 n개를 초과하게 된다. 따라서 동일하게 end를 mid-1로 설정한다. 

Step 3

start = 1, end = 5, mid = 3 일 때 

0

2

11

14

17

21

25

여기서는 삭제되는 값이 n개보다 작으므로 start를 mid+1로 설정해서 가장 큰 mid 값을 찾아준다. 

Step 4 

start = 4, end = 5, mid = 4 일 때 

0

2

11

14

17

21

25

여기서 삭제되는 값은 n개와 동일하다. 따라서 answer에 mid값을 저장해주고 출력하면 답을 찾을 수 있다. 

---

My Code

def solution(distance, rocks, n):
    answer = 0
    
    rocks.append(distance)
    rocks.sort()
    
    start = 1 
    end = distance 
    
    while start <= end:
        mid = (start + end) // 2 
        
        previous = 0 
        count = 0
        for rock in rocks:
            if rock - previous < mid:
                count += 1
                if count > n: break 
            else:
                previous = rock
        
        if count > n:
            end = mid - 1 
        else:
            answer = mid 
            start = mid + 1
    
    return answer