[프로그래머스] 징검다리 - 파이썬(python)

 

도저히 이분탐색으로 푸는 방법을 생각해내지 못해, 다른 분들의 풀이를 참고하여 아이디어를 얻은 채, 다시 코드를 작성하였다.

 

 

풀이

def solution(distance, rocks, n):
    answer = 0
    start, end = 0, distance
    
    rocks.append(distance) # 맨 뒤 거리도 계산할 수 있도록 한다
    rocks.sort() # 바위 정렬
    
    #이분 탐색
    while start <= end: 
        mid = (start + end) // 2 # 중간값 -> 바위 간격의 최솟값
        
        del_stones = 0 # 제거한 돌 개수
        pre_stone = 0 # 기준이되는 돌(시작지점)
        min_dis = distance
        
        for rock in rocks: 
            dis = rock - pre_stone # 현재 바위 - 이전 바위 사이 간격
            
            if dis <  mid: # 돌사이 간격이 mid 보다 작으면 제거한다. mid 는 바위 간격의 최솟값이므로, 이보다 더 작은 값이 존재할 수 없으므로 제거해야 한다.
                del_stones += 1 
            else: # 아니라면 현재 돌을 새로운 기준으로 하여, 계속 탐색한다.
                pre_stone = rock
                min_dis = min(dis, min_dis)
             
            if del_stones > n: #제거된 돌이 문제 조건 보다 크면 for문을 나온다
            	break
                
        if del_stones > n: # 제거된 돌이 너무 많으면 가정한 바위 간격의 최솟값(mid)이 큰 것이므로 범위를 줄인다.
            end = mid - 1
            
        else: # 반대라면 큰 쪽으로 줄인다.
            answer = min_dis
            start = mid + 1
            
    return answer

• 마지막 도착지점과의 간격도 생각해야 하므로, 도착지점을 마지막 바위로 간주하여 추가하였다.
• mid 는 바위 간격의 최솟값을 지정한 것이다.
• mid 이라는 간격의 최솟값을 만들기 위해 몇 개의 바위를 제거해야 하는지를 탐색한 후, 제거된 바위가 N보다 크다면mid 값을 줄이고, 그렇지 않다면 mid 값을 늘린 후 계속해서 탐색하는 방법이다.
• 만약, (기준이 되는 돌 - 현재돌)의 간격이 mid 보다 작다면? mid는 간격의 최솟값을 뜻하는데, 이보다 더 작은 값이 존재할 수 없으므로 해당 바위를 제거한다.
• 만약, mid 보다 크거나 같다면? 기준바위~현재바위 까지의 간격이 min_dis(최소 간격) 값보다 작다면 min_dis 를 갱신한다. 그런 다음 현재 바위를 기준 바위로 삼고, 계속해서 나머지 바위들을 탐색한다.
• 모든 바위들에 대해 탐색한 후, 만약 제거된 돌의 개수가 N보다 크다면? mid 가 큰 것이므로 범위를 줄이기 위해 end 값을 end = mid - 1로 지정한다.
• 만약 제거된 돌의 개수가 N 이하라면, min_dis (최소 간격) 을 answer 로 지정하고, start = mid + 1 로 지정하여 계속 탐색한다.