프로그래머스 [Lv. 4] 징검다리 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

def solution(distance, rocks, n):
    answer = 0
    minD, maxD = 0, distance
    rocks.sort()
    rocks.append(distance)
    
    # 이분 탐색 시작
    while minD <= maxD:
        searchD = (minD + maxD) // 2
        currentH = cnt = 0 # cnt는 제거할 바위 수
        
        # tmp distance
        for rockH in rocks:
            currentD = rockH - currentH
            if currentD < searchD:
                cnt += 1
            else:
                currentH = rockH
                if searchD > currentD:
                    searchD = currentD
            if cnt > n:
                maxD = searchD - 1
                break
        else:
            answer = searchD
            minD = searchD + 1
    
    return answer

풀이 방법

1. 최소값과 최대값을 정해준다.
2. distance를 append해주는 이유는 도착점과의 거리 계산을 위해서다.
3. 이분탐색의 기본인 정렬을 해주고 시작한다.
4. 현재 높이와 제거할 바위 수를 0으로 초기화 한다.
   1. 현재 바위는 0인 시작지점과의 거리계산으로 시작된다.
   2. 현재 바위의 높이에서 현재 위치를 뺀값이 currentD
   3. 현재 거리가 찾고자 하는 거리보다 작다면 바위를 제거한다.
   4. 하지만 찾고자 하는 거리보다 크거나 같다면 현재 위치를 갱신해준다.
   5. 그리고 searchD를 currentD로 바꿔준다.
5. 제거한 바위의 수가 제거 가능한 바위의 수인 n보다 클 경우에
   1. 범위를 줄여주기 위해서 maxD의 값을 searchD - 1로 바꾼다.
   2. break를 통해서 거리계산을 빠져나온다.
6. break가 걸리지 않고 빠져나온 경우에
   1. 현재 발견한 거리 searchD는 유효하다는 말이므로 answer에 저장하고
   2. searchD보다 큰 값이 있을 수 있으므로 minD의 값을 높여준다.

느낀점

• 이분탐색은 기본 알고리즘이지만 접근 하는 방식이 까다롭다고 느껴진다.
• 어느 부분에서 반복문을 실행할지 계산할지를 아직은 경험이 부족해서 그런것 같다.
• 앞으로 이분탐색 문제를 많이 풀어보고 경험치를 늘려야겠다.