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

징검다리 | Lv.4
https://school.programmers.co.kr/learn/courses/30/lessons/43236

 

 

작성 코드 (시간 초과)

 

from itertools import combinations


def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    
    # 제거할 rock을 combination으로 생성
    combination = list(combinations(rocks, n))
    for comb in combination:
        min_dist = distance
        before = 0
        for rock in rocks:
        
            # rock 이 comb에 없으면, 즉 제거할 바위가 아니면
            if rock not in comb:
                min_dist = min(min_dist, rock - before) // min_dist 갱신
                before = rock // 해당 바위를 지났으니 before 갱신
        min_dist = min(min_dist, distance - before)
        answer = max(answer, min_dist)
    return answer

 

• 당연히 시간 초과일 것이라 생각은 함...
• 어떤 기준으로 이분 탐색을 해야 할지 감이 안 잡힘

 

 

이상 코드

 

def solution(distance, rocks, n):
    
    left, right = 0, distance
    # rocks의 마지막 돌과 도착 돌 사이의 거리도 고려해야 함
    rocks.append(distance)
    rocks.sort()
    
    while left <= right:
        mid = (left + right) // 2
        
        # 제거한 돌의 개수
        del_stones_cnt = 0
        # 거리를 잴 바로 이전의 돌
        pre_stone = 0
        
        for rock in rocks:
            
            # 이전의 돌과의 거리가 mid 값보다 작다면
            if (rock - pre_stone) < mid:
                del_stones_cnt += 1 # 돌을 제거함
                
            else: # 이전의 돌과의 거리가 mid 보다 크거나 같다면 해당 돌을 이후의 돌과 비교하도록 pre_stone 으로 지정
                pre_stone = rock
            
            # 만약 제거한 돌이 n보다 크다면 더이상 돌 필요가 없음    
            if del_stones_cnt > n:
                break
        
        # 만약 제거한 돌이 n보다 크다면 mid 값을 줄여야 함
        if del_stones_cnt > n:
            right = mid - 1
        
        # 만약 제거한 돌이 n보다 작거나 같다면 mid 값을 늘려도 됨 (만족한다)
        else:
            left = mid + 1
            
    return right

 

• answer은 1과 distance 사이!! → 최솟값이 될 수 있는 걸 이분탐색. 어차피 답은 그 안에 있으니!
• mid 가 거리 차이의 최댓값이 된다면,  mid 보다 작은 값들도 후보임
  5가 답(최소 거리 중 가장 큰 값)이라면 4도 당연히 답이 될 수 있음
  but 5를 찾았는데 굳이 그 이하를 찾을 필요는 없음 어차피 가장 큰 값을 찾아야 하는 거니까!
• mid 가 거리 차이의 최댓값이 되지 않는다면 (n개의 돌을 삭제하더라도 해당 mid보다 작다면) mid보다 큰 값들은 당연히 답이 될 수 없음
  5가 답을 만족 못 시켰는데 6은 당연히 만족 못 시킴 

1	4	8	14
mid = 5 : 거리 차이의 최솟값은 4로 mid 값(5)을 만족 못 시킴 → 당연 6은 불가능 mid = 3 : 거리 차이의 최솟값은 4로 mid 값(3)을 만족 시킴 → 당연 2는 가능