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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43236

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

 

프로그래머스 기준 Level 4인, 약간 어려운 문제입니다.

 

문제 내에서 총 거리가 주어지고 (distance), 각 바위의 위치가 주어집니다. 이후 제거해야 하는 바위의 수 (n)이 주어집니다.

n개의 바위를 제거한 후 시작점 - 각 바위 사이 - 도착점 사이의 거리를 구했을 때, 어떤 바위를 제거했느냐에 따라 각 바위 사이 거리가 달라집니다. 이때의 최소값을 a라고 하면,

모든 경우의 a값 중 최대가 되는 값이 정답이 됩니다.

 

이번 문제 역시 다른 이분 탐색 문제와 마찬가지로 이분 탐색 기준을 어떻게 잡을지 고민을 많이 했습니다.

여기 글을 참고하여 아이디어를 생각해 내고, 이를 코드로 옮겼습니다.

제가 잡은 기준을 다음과 같습니다.

초기 left = 1, right = distance로 둡니다. 바위 사이 거리의 최소와 최대값을 잡은 것입니다.

이후 loop를 반복하며 mid = (left + right) / 2로 하고, 두 바위 사이의 거리가 mid보다 작은 경우 해당 바위를 제거합니다.

바위를 제거하는 경우 제거한 바위 수를 세고, 제거하지 않는 경우 이전 바위를 갱신합니다.

 

제거한 돌의 개수가 n개 초과인 경우, right = mid - 1 을 통해, 기준이 되는 바위 사이 간격을 줄입니다.

제거한 돌의 개수가 n개 이하인 경우, left = mid + 1을 통해, 기준이 되는 바위 사이 간격을 늘립니다.

 

왜 제거한 돌의 개수가 'n개와 같을 때' 가 아닌 'n개 이하인 경우' 일까요?
바위 사이의 간격이 mid보다 작은 경우를 모두 제거했을 때, 남은 바위들의 간격은 mid 이상이 됩니다.

즉, 여기서 바위를 더 제거해도, 바위들의 간격은 반드시 mid 이상이 됩니다.

따라서 n개보다 적은 경우, 어떤 바위를 제거해도 주어진 조건을 만족할 수 있으므로, 조건에 포함시킵니다.

 

채점 결과

이분 탐색을 떠올리고 모델링 하는게 제일 어려운 것 같습니다 ㅠ