[Python3]프로그래머스_징검다리

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

풀이출처: https://ssocoit.tistory.com/61

접근법

먼저 내가 생각했던 접근법들이다.

1. 바위의개수 중 n개를 제거하는 모든 경우를 검사한다.

• 시간초과가 예상되어 시도하지 않았다.

2. 바위 간의 거리들을 계산하여 낮은 순서대로 제거하며 거리간의 변화를 반영시켜 다시 계산한다.

• 이 방법은 구현이 어려울뿐만 아니라 같은 최소거리들이 여러개라면 어떤 것을 우선적으로 제거해야할 지 알기 어려웠다.

그래서 다른사람의 코드를 보며 풀었기 때문에 출처와 함께 간략하게 이해한 내용들을 적어보았다.

바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return

• 거리가 answer 보다 작거나 같은 바위들은 n개 제거됐다는 뜻이다.

• 어떤 값 기준으로 바위들을 제거해 나갈때 바위들이 k개 제거할 수 있다면 k를 기준으로 범위를 좁힐 수 있다.

• 거리는 최소 1, 최대 distance 까지이고 중앙값 mid를 기준으로 바위를 몇개까지 제거해야하는 지 확인 후 범위를 좁히는 것이 포인트

코드

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