[프로그래머스] 징검다리, 파이썬

💡 문제 해결 아이디어

🛠 피드백

• 다른 사람의 풀이를 보고 해결한 문제이다!
• 문제를 다르게 해석하자면, n개의 제거를 요구하는 적절한 거리의 커트라인 중 최적의 값을 찾는 문제이다
• 커트라인이 너무 많은 바위를 제거하게 했다면 커트라인이 너무 높은 것이고, 너무 적은 바위를 제거하게 했다면 커트라인이 너무 낮은 것이다.
• 딱 n개의 바위를 제거했더라도, 커트라인은 그보다 더 높을 수 있음을 인지하자

💻 작성된 코드(수정)

def solution(distance, rocks, n):
	# 커트라인 최솟값 = 1
    left = 1
    # 커트라인 최댓값 = distance
    right = distance
    
    # 바위 위치를 정렬하고, 도착지점 append
    rocks.sort()
    rocks.append(distance)
    
    while left <= right:
        mid = (left+right)//2
        # 제거한 바위 개수
        delete = 0
        # 이전 바위의 위치
        prev_rock = 0
        for rock in rocks:
            dist = rock - prev_rock
            # 거리가 커트라인 보다 작다면, 바위를 제거
            if dist < mid:
                delete += 1
                # 제거한 바위가 너무 많다면 break
                if delete > n:
                    break
            # 바위를 제거하지 않았다면, prev_rock을 갱신
            else:
                prev_rock = rock
                
        # 초과 제거한 경우 : 커트라인이 너무 높음
        if delete > n:
            right = mid -1
        # 이하 제거한 경우 : 커트라인이 적절하거나 너무 낮음
        else:
            answer = mid
            left = mid + 1
    return answer

• 총 2가지를 얻어갈 수 있었던 문제

1. input의 최대길이가 지나치게 길고, 특정 값을 찾아야 하는 문제라면 이분탐색을 의심해보자
2. 이분탐색의 전반적인 구조를 외우도록 하자 (left, right, while, for, break, if...)