징검다리

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

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

될리가 없지만... 

이걸로 풀리면 프로그래머스 level 1~2 정도의 문제라 할 수 있다. 

문제를 코드로 옮겼더니 풀리더라 = 레벨 2 이하. 

from itertools import combinations


def solution(distance, rocks, n):
    rocks.extend((0, distance))
    rocks.sort()
    lengths = []
    for i in range(len(rocks) - 1):
        lengths.append(rocks[i + 1] - rocks[i])
    min_vals = []
    for pop_rocks in combinations(range(len(lengths) - 1), n):
        array = lengths[:]
        for each in pop_rocks:
            array[each + 1] += array[each]
            array[each] = float('inf')
        min_vals.append(min(array))
    return max(min_vals)

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (0.03ms, 10.2MB)

파라메트릭 서치로 풀어야하는 문제다. 

https://marades.tistory.com/7

이진탐색(Binary Search)와 파라메트릭서치(Parametric Search)

바위 사이 거리를 기준으로 문제를 푼다. 

def solution(distance, rocks, n):
    def check(target_interval):
        """바위를 n번 이하로 삭제해서,
        바위 사이 거리를 목표 거리(target interval)이상으로 만들수 있나?"""
        prev_rock = pop_count = 0  # 이전 바위(시작 지점), 바위 삭제 횟수
        for rock in rocks:
            if rock - prev_rock < target_interval:
                pop_count += 1
                if pop_count > n:
                    return False
            else:
                prev_rock = rock
        return True

    rocks.sort()
    left, right = 1, distance
    while left <= right:
        mid = (left + right) // 2
        if check(mid):  # 모든 바위 사이 거리를 mid 이상으로 만들 수 있다면 거리를 늘려보자.
            left = mid + 1
        else:
            right = mid - 1
    return right

테스트 1 〉	통과 (0.44ms, 10.1MB)
테스트 2 〉	통과 (0.32ms, 10.4MB)
테스트 3 〉	통과 (0.78ms, 10.3MB)
테스트 4 〉	통과 (6.15ms, 10.5MB)
테스트 5 〉	통과 (7.26ms, 10.4MB)
테스트 6 〉	통과 (32.21ms, 13.1MB)
테스트 7 〉	통과 (71.79ms, 14.4MB)
테스트 8 〉	통과 (161.55ms, 14.6MB)
테스트 9 〉	통과 (0.01ms, 10.1MB)

어려우면 다음 문제를 먼저 풀어보자.. 

https://programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스