[Programmers] 징검다리

문제

요약

distance 만큼의 거리 사이에 rocks의 돌들이 있음.

rocks에서 임의의 n개 돌을 제거했을 때, 돌 사이 거리의 최솟값의  최대값은 몇인가?

 

원본

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

프로그래머스

 

---

풀이

이번에도 스스로 풀지 못했다 ㅠㅜ

언제쯤 알아서 척척 스스로 어른이가 되는가,,,

 

이번 문제는 그래도 어디서 이분탐색을 해야할지는 어떻게 할지 접근 방식이 근접했다.

돌이 일단 섞여 있으니 돌을 정렬 해주어야 하고, 돌에서 이진탐색을 한다.

예시를 보니 출발지점에서 돌까지, 돌에서 도착지점까지 들어가고 나가는 거리도 포함해서 생각해야 한다.

 

여기까지는 알았는데 임의의 거리를 다른 돌들과 비교하는 부분에 대해서 이해가 잘 안 갔다.

1. 임의의 거리 이분탐색해서 지정

2. 기준은 0부터 시작, 돌을 순회하면서 기준까지 거리가 임의값보다 작으면 제거하는 돌에 추가

3. 아니면 기준돌을 현재 돌로 갱신

4. 다 돌고 제거하는 돌 개수가 많으면 작은 값으로 다시 이분탐색

5. 아니면 answer 갱신과 큰 값으로 다시 이분탐색

6. 반복

 

이해가 안될때는 손으로 이해하자...! ㅎ

풀다 보니 이분탐색은 이분탐색 자체보다 어떻게 값을 비교하는지 비교 방법을 떠올리는게 메인인것 같다.

IQ가 낮을까,,,,나..? 

def solution(distance, rocks, n):
    answer = 0
    rocks.append(distance)
    rocks.sort()
    lw, up = 1, distance
    
    while lw <= up :
        mid = (lw+up) // 2
        q = 0
        d = 0
        
        for r in rocks:
            if r - q < mid:
                d += 1
            else:
                q = r
                
            if d > n:
                break
                
        if d > n:
            up = mid -1
        else:
            answer = mid
            lw = mid + 1

    return answer