Programmers | 징검다리 - Python

soo5717·2021년 5월 12일

1. 개념 정리

1.1 이진 탐색 (Binary Search)

정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 찾으려는 데이터와 중간 점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색이다.

탐색할 때마다 탐색 해야 할 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logn)이다.

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) //2
        
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
	return None

2. 문제 설명

2.1 징검다리

출발지점부터 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 함수를 작성해주세요.

2.2 제한 조건

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

2.3 입출력 예시

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

3. 풀이 과정

바위를 제거한 후 각 지점 사이의 거리의 최솟값이 최대가 되게 하는 값을 구하는 문제이다. 코드의 구현은 어렵지 않지만, 풀이 방법을 생각해내는 게 어려운 문제였다.

문제에서 제공되는 테스트 케이스가 부족해서 임의로 추가해서 풀어보았다. (마지막 테스트 케이스는 프로그래머스에 다른 분이 올려준 케이스를 추가한 것이다.)

3.1 탐욕법 : 실패😂

일단은 문제를 딱 봤을 때 생각나는 풀이 방식은 다음 2가지였다.

바위를 제거하는 가능한 모든 경우의 수 구하기

문제에서 의도하는 바가 아닌 듯하고, 시간 초과가 날 것 같아 시도하지 않았다.

바위 사이의 간격이 가장 작은 바위를 제거하는 방식 (그리디 알고리즘)

풀이는 시도했으나 현재의 최적 해가 최종적인 최적의 해가 아니라 실패하였다.

바위 사이의 간격을 담은 rock_distance라는 배열을 만들고 n번 순회하면서 rock_distance 중 가장 작은 간격을 제거한 후 최종적으로는 rock_distance의 최솟값을 반환하는 방식이다.

하지만, 현재의 최적 해가 결론적으로 최적의 해를 보장하지 않기 때문에 실패한 풀이 방식이었다. 위에서 추가한 테스트 케이스 중 distance = 18, rocks = [2, 8, 9, 10, 11, 12, 13], n = 2의 경우 9를 제외한 나머지 바위가 모두 제거되어서 answer = 9를 반환해야 하는데 아래 풀이 방식대로 할 경우 8을 반환하여 실패하였다.

전체 코드 (python)

def solution(distance, rocks, n):
    rocks.extend([0, distance])
    rocks.sort()

    # rocks = [0, 2, 11, 14, 17, 21, 25]
    # rock_distance = [2, 9, 3, 3, 4, 4]
    rock_distance = [rocks[i + 1] - rocks[i] for i in range(len(rocks)-1)]

    for _ in range(n):
        idx=  rock_distance.index(min(rock_distance[:-1]))
        rock_distance[idx + 1] += rock_distance[idx]
        del rock_distance[idx]
            
    return min(rock_distance)

실행 결과

3.2 이진 탐색 : 성공😋

제한 조건이 많은 것을 보고 이진 탐색을 떠올릴 수 있었지만, 방식이 잘 생각나지 않았었다. 주어진 조건에 맞춰서 start와 end를 설정하고 mid의 기준을 정해야 하는데 mid의 기준을 어떤 식으로 잡아야 할지가 어려웠던 것 같다. 이것이 코딩테스트다 책에서 떡볶이 떡 만들기 문제를 통해서 풀이 힌트를 얻을 수 있었고 성공할 수 있었다!

3.2.1 떡볶이 떡 만들기

높이가 다양한 떡을 높이 h로 한 번에 잘라서 잘린 떡의 길이의 합이 손님이 요청한 M만큼의 떡을 얻을 수 있어야 하는데 그때의 h의 최댓값을 구하는 문제였다. 이진 탐색을 통해 풀이할 수 있었다.

start, end는 h의 최솟값과 최댓값(가장 긴 떡의 길이)으로 정한다.

start <= end 일 때까지 반복하면서

mid일 때의 잘린 떡의 양을 계산한다.

잘린 떡이 부족한 경우 더 많이 자를 수 있도록 end의 값을 mid - 1로 지정해 왼쪽을 탐색할 수 있게 한다.

잘린 떡이 충분하거나 많을 경우 더 적게 자를 수 있도록 start의 값을 mid + 1로 지정해 오른쪽을 탐색할 수 있게 한다.

3.2.2 탐색 기준 결정

위의 풀이를 보고 아래와 같이 start와 end, 그리고 mid의 탐색 기준을 정할 수 있었다.

start와 end는 구하고자 하는 값의 최솟값, 최댓값으로 지정한다.

바위는 중첩되지 않으니 각 지점 사이의 거리는 최소 1이상이어야 하고, 바위가 없을 경우에는 distance가 각 지점 사이의 거리가 되기 때문에 answer의 값은 1 ~ distance 사이에 있다.

mid(start와 end의 중간)를 answer로 가정하고 탐색을 하면서 mid보다 작은 간격을 가지는 바위를 제거한다.

위에서 제거한 바위의 수를 세서 입력 조건의 n과 비교를 한다.

더 많이 파괴되었을 경우는 end = mid - 1으로 지정해 왼쪽을 탐색할 수 있게 한다.

같거나 더 적게 파괴되었을 경우에는 start = mid + 1로 지정해 오른쪽을 탐색할 수 있게 한다.

3.2.3 풀이 예시

2번에서 mid보다 작은 간격을 가지는 바위를 제거하는 경우는 덕봇기의 코딩세상님의 풀이가 자세히 설명되어 있어서 참고하면 좋을 것 같다.

rocks을 순차적으로 탐색해 가면서 기준이 되는 이전 바위 prev_rock과의 간격이 mid보다 작을 경우 바위를 제거했다고 가정하고 cnt += 1을 하고, 만약 preve_rock과의 간격이 mid 보다 크거나 같을 경우는 제거할 필요가 없으니 해당 바위로 prev_rock을 업데이트 하는 방식이다.

mid = 4 일 경우 2와 14 지점에 있는 바위를 제거한다.

3.2.4 코드 구현

전체 코드 (python)

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    
    answer = 0
    start, end = 1, distance # answer은 1 ~ distance 사이에 있음
    while start <= end:
        mid = (start + end) // 2
        
        # 부서진 바위의 수 세기
        cnt_rock, prev_rock = 0, 0
        # 0 / 2 11 14 17 21 / 25
        for rock in rocks:
            if rock - prev_rock < mid:
                cnt_rock += 1
            else:
                prev_rock = rock
            
        if cnt_rock > n: # 더 많이 파괴되었을 경우
            end = mid - 1
        else: # 같거나 더 작게 파괴되었을 경우
            answer = mid
            start = mid + 1
            
    return answer

실행 결과

4. 핵심 정리

4.1 🔥 최종 풀이 🔥

정렬 후 이진 탐색을 활용하는 풀이로, 시간 복잡도는 다음과 같다.

정렬 O(nlogn) + 이진 탐색 O(log(distance))

def solution(distance, rocks, n):
    rocks.sort()
    rocks.append(distance)
    
    answer = 0
    start, end = 1, distance 
    while start <= end:
        mid = (start + end) // 2
        
        # 부서진 바위의 수 세기
        cnt_rock = 0
        prev_rock = 0
        for rock in rocks:
            if rock - prev_rock < mid:
                cnt_rock += 1
            else:
                prev_rock = rock
            
        if cnt_rock > n:
            end = mid - 1
        else: 
            answer = mid
            start = mid + 1
            
    return answer