프로그래머스 징검다리 (파이썬)

이분 탐색, Level 4

 

문제: https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리

문제 설명

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

 

제출 코드 (정답)

def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    left, right = 0, distance
    while left <= right:
        mid = (left+right)//2
        cur = 0 # 왼쪽 기준 바위 위치
        removeCnt = 0
        for rock in rocks:
            dist = rock - cur # 왼쪽 바위와 현재 돌의 거리 
            if dist < mid: #제거 되는 바위
                removeCnt += 1
                continue
            else:
                cur = rock
        #남겨야 하는 바위 수        
        if removeCnt > n: # 제거 되는 바위가 많거나 같다, mid값을 늘려 최대 거리 간격을 늘려서 바위를 덜 제거하기
            right = mid - 1
        else: # 제거되는 바위가 딱 적절하거나 적다, mid값을 줄여 최대 거리 간격을 줄여서 바위 더 제거
            answer = mid
            left = mid + 1
    return answer

 

결과 및 정리

이분 탐색이었지만 전혀 정답이 생각나지 않아 검색의 도움을 받았습니다.

하지만 해설을 보면서도 이해가 잘 안되어 여러 번 생각하고 차근차근 처음부터 이분 탐색을 써 내려가 보니 해설이 이해되었습니다.

 

이분 탐색은 범위와 기준이 가장 중요한 것 같습니다. 

이분 탐색을 배열 안의 원소를 빠르게 찾기 위한 방법도 있지만 이 경우는 이분 탐색의 기본을 활용해서 mid라는 중간 값이 정답이라고 설정하고 풀어서 찾은 돌의 개수가 n보다 작냐 크냐로 mid를 조절해야 합니다.

범위는 0부터 distance까지로 정하고, mid는 인덱스가 아니라 왼쪽 돌과의 거리가 최소가 될 경우를 기준으로 잡고 풀어야합니다.

그러기 위해 새로운 변수 cur를 설정해서 만약 mid보다 짧은 거리의 돌과의 거리가 나오면 그 돌부터 다음 돌까지의 거리를 측정합니다.

즉, mid가 짧고 긴 것의 기준이 됩니다. 이 핵심을 이해하기까지 많은 시간이 걸렸습니다.

그리고 제거 되는 돌의 개수가 n 보다 적을 경우는 기준인 mid를 길게 잡아 너무 많은 돌을 제거한 경우이고

돌의 개수 n 이하일 경우는 mid를 너무 짧게 정해 돌을 제거하지 않은 경우입니다.

 

제거하는 돌의 수가 n개 일 때와 n 미만일 때를 나누지 않고 이하로 묶어 같이 계산하는 이유는 최소들 중에서 최댓값이 나오는 경우를 찾기 때문에 최소가 되기만 하면 때마다 저장하고 계속 값을 갱신시켜야 합니다.