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

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

프로그래머스

 

이분탐색 문제인걸 알고 풀어도 어려운 문제였다.

 

알고리즘을 어떻게 적용해야 할지 아이디어가 떠오르지 않아서 힌트를 찾아봤는데

 

힌트를 보고도 다른 부분에서 막혀서 3시간 정도를 고민하다가 정답을 참고했다.

 

내가 생각한 풀이

 

n개의 돌을 제거할때 어떤 돌을 제거하냐에 따라 거리의 최소값이 달라지므로

 

n개의 돌을 제거하는 모든 경우의 수를 구하는 방법을 생각했지만

 

제거 가능한 돌의 개수가 너무 많아서 시간이 초과될 것이 분명했다.

 

그래서 돌을 제거하고 남은 거리의 최솟값을 최대한으로 높이기 위해

 

처음부터 가장 최소 거리를 만드는 돌을 제거하여 거리를 늘리는 방법을 생각했다.

 

하지만 그렇게해도 최소 거리를 만드는 돌 중 어떤 돌을 제거하느냐에 따라

 

남아있는 돌 사이 거리의 최댓값이 달라져 처음 생각했던 방법과 크게 다르지 않았다.

 

풀이

 

핵심 아이디어는 어떤 임의의 값(X)을 돌 사이 거리 중 가장 작은 값으로 만들기 위해서

 

과연 몇 개의 돌을 제거해야 하는가? 를 생각하는 것이다.

 

사실, 주어지는 distance 값의 범위가 1이상 1,000,000,000 이하인 것을 봤을때

 

최적화할 값을 거리의 최솟값으로 정하고 특정 조건을 만족시키는 값을 찾아야 한다는 힌트를 얻을 수 있다.

 

만약 돌 사이의 거리를 전부 X 이상으로 만들기 위해 제거한 돌이 n개 보다 작거나 같다면

 

돌을 기준보다 적게 제거했으므로 X를 높여보는 것이다. 

 

반대로 제거한 돌이 n개보다 크다면 모든 돌 사이 거리를 X 이상으로 맞추는데

 

예상보다 많은 돌을 제거했다는 의미이므로 X를 낮춘다.

 

그렇다면 모든 돌 사이의 거리를 X 이상으로 만들기 위해서는 어떻게 해야할까?

 

돌의 위치를 오름차순으로 정렬하고 출발지점을 기준으로 돌들 사이의 거리를 더해나간다.

더한 값이 X 이상이 되면 앞의 돌들을 제거해서 거리를 늘렸다는 뜻이므로

 

현재 돌을 새로운 기준으로 잡고 동일하게 다음 돌들 사이 거리를 도착지점까지 더해나간다.

 

지나온 돌은 이미 X이상의 거리를 만들어놨기 때문에 신경쓸 필요가 없다.

 

def solution(distance, rocks, n):
    answer = 0
    rocks.append(distance)
    rocks.sort()
    s, e = 1, distance
    while s <= e :
        m = (s+e) // 2
        cnt, d = 0, 0
        for rock in rocks:
            if rock-d < m:
                cnt += 1
            else:
                d = rock 
        if cnt > n :
            e = m-1
        else:
            answer = m
            s = m+1
    return answer