파이썬(Python) 알고리즘 문제풀이 징검다리 [프로그래머스 / 이분탐색]

출처) 프로그래머스 Facebook

문제 설명

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

 

 

풀이 코드

이분 탐색 문제는 항상 어떤 것을 임의의 기준 값으로 삼아야하는지 고민을 해야한다.

 

바위들 간 거리 간격 중 최대 값을 구하기 위해선 바위를 하나 씩 제거한 뒤 값을 하나씩 비교해야하는데, 바위는 최대 5만개, 총 거리는 최대 10억까지 주어지기 때문에 시간 복잡도에서 절대 통과할 수 없다. 이럴 땐 생각이 전환이 필요한데, 이 바위 저 바위를 제거했을 때 나올 수 있는 모든 경우의 최소 값들 중 최대 값을 구하는게 아니라, 미리 임의의 최소 값을 기준으로 잡고, 이 기준으로 바위를 몇 개 제거할 수 있는지 ? 로 거꾸로 생각하는 것이다. 이렇게 한다면 바위를 제거하는 경우에서 나올 수 있는 최소 값들을 갱신 -> 최대 값을 구하면 되는 문제

 

그렇다면 임의의 최소 값은 어떻게 정할 수 있을까 ? 좀 꼼수인 것 같은데 이렇게 대놓고 이분 탐색인 문제는 distance 처럼 10억이라는 큰 값이 주어지는데, 여기서 임의 값을 구해보는 식으로 진행하면 왠만한 문제는 풀리는 듯 ..

 

여기까지 코드는 아래와 같다.

최대 값을 갱신하기 위해 answer 변수를 -1e15 로 초기화, start 는 0, end 는 distance 로 초기화한다.

그리고 이진 탐색을 위해 rocks 리스트를 오름차순 정렬하고, while 반복문을 설정한다.

def solution(distance, rocks, n):
    answer = -1e15
    start, end = 0, distance
    rocks.sort()

    while start <= end:
        mid = (start + end) // 2

 

 

이제 임의 값 mid 를 구했으니 바위를 몇 개 제거할 수 있는지 체크해야한다. 문제에서 제공한 테스트 케이스를 통해 예를 들어보자.

rocks 를 오름차순 정렬했으니 rocks = [2, 11, 14, 17, 21], start = 0, end = 25, mid = 12 라는 값이 존재한다.

 

start = 0, end = 25 니까 0, 2, 11, 14, 17, 21, 25 라고 생각하면 되고, mid 값이 12 니까 현재 출발지(0) 에서 도착지(2) 까지 구간 거리를 계산한다면 mid 값 보다 작다. 이 말은 mid 값이 최소 값이 아니라는 뜻이니까 도착지(2) 를 제거해서 구간 길이를 늘려줘야 한다. 즉, 0 ~ 2 구간이 아니라 0 ~ 11 구간으로 만들면 된다는 뜻.

 

제공된 테스트 케이스 대로 진행하다보면 바위가 지워지다 출발지(0) ~ 도착지(14) 구간 거리와 mid 를 비교하게 되고 이때 구간 거리가 mid 값 보다 커진다. 이 말은 mid 값이 일단은 최소 값이라는 뜻이고 지금까지의 출발지(0) 기준으로 바위들 간(2, 11) 구간 거리를 mid 값과 하나하나 비교했을 때 바위를 제거하는 식으로 (여기까지 2, 11 바위가 제거됐음) 구간 거리를 늘리다가 출발지(0) 기준으로 구간 거리를 더 이상 증가시키지 않아도 된다는 뜻이므로 도착지 바위를 출발지로 갱신하면 된다. 

(쉽게 말해서 처음 출발지(0) 기준 다른 바위들과 차례로 비교해 11 구간까지 mid 값 보다 작은 구간을 모조리 없앴으니까 다음 바위(14) 를 기준으로 또 최소 값 mid 보다 작은 구간을 판단할 수 있도록 출발지를 갱신한 것임)

 

여기까지 코드는 아래와 같다. 파라메트릭 서치 유형 문제 풀이와 유사하다는 걸 느낄 수 있을 듯 ??

우리는 mid 값을 distance 값 까지 비교했으니까 rocks 배열에 distance 값을 꼭 추가해줘야 한다. (이거 추가안해서 계속 틀림 ;;)

이런 식으로 풀면 대게 맞을텐데, 틀릴 수도 있다. 나도 계속 틀려서 질문하기를 보고 알았는데 지문에 없지만 이게 무조건 n 개의 바위를 제거했을 때 계산할 수 있는 구간의 최소 값들 중 최대 값을 구하는게 아니라 바위를 n 개 까지 제거할 수 있다. 라고 가정하고 풀이해야 풀린다.

그니까 n = 2 라고 주어진 경우 바위 2개를 지워서 나오는 구간 거리들의 최소 값 중 최대 값보다 바위 1개를 지우거나 0개 지우거나 했을 때 나오는 구간 거리들의 최소 값 중 최대 값이 더 크다면 바위를 n 만큼 지웠을 때 최대 값이 꼭 정답은 아니라는 소리임 (???)

지문이 개떡같긴한데 논리적으로 맞는데 안풀린다 싶으면 mid 값을 조정하는 부분 분기문을 적당히 수정해주자 ..

def solution(distance, rocks, n):
    answer = -1e15
    start, end = 0, distance
    rocks.sort()
    rocks.append(distance)

    while start <= end:
        mid = (start + end) // 2
        current_start_rock_location = 0
        delete_rock_count = 0

        for rock in rocks:
            # 현재 출발위치, 바위 기준 구간 거리가 임의 최소값 mid 보다 작은 경우,
            # 임의 최소값 mid 가 최소 값이 아니게 되니 최소 값으로 만들어주기 위해서
            # 바위를 하나 지워준다. 이러면 해당 구간 거리가 늘어나게 되니까
            if rock - pre_rock_location < mid:
                delete_rock_count += 1

            # 현재 출발위치, 바위 기준 구간 거리가 임의 최소값 mid 보다 큰 경우,
            # 현재 출발위치에서 바위를 지워 구간 거리를 더 이상 늘릴 필요가 없고
            # 현재 바위를 출발 바위로 갱신하고 새로운 출발 기준에서 다음 바위의 구간 거리를 계산하고
            # 임의 최소값 mid 와 비교해야한다.
            else:
                current_start_rock_location = rock

        # 임의 최소값 mid 를 기준으로 했을 떄 몇 개의 바위를 지워야하는지 구해졌으니
        # 임의 최소값 mid 를 줄일지 늘릴지 판단한다.

        # 바위를 n 개 보다 많이 제거했을 때 mid 값을 충족할 수 있었다면 mid 값을 줄인다.
        if delete_rock_count > n:
            end = mid - 1

        # n 개 보다 적게 제거 또는 n 개만큼 제거했을 때 mid 값을 충족할 수 있었다면 mid 값을 높인다.
        # 파라메트릭 서치 문제에 익숙하다면 금방 이해할 수 있을 듯
        elif delete_rock_count <= n:
            start = end + 1
            answer = max(answer, mid)

    return answer