프로그래머스 (징검다리) with python

 

---

이 문제의 경우 먼저는  제한사항을 보고 도착지점까지의 거리 distance가 10억 이하라는 것을 보고 이분탐색으로 풀어야한다는 것을 유추해내는 것이 좋다. 그러나 이후 문제에서 이분탐색을 어떻게 써야할 지가 너무나 막막하다

처음에는 combination을 통해 바위의 위치를 두 개 선택하여 제거하고 난 뒤 이분탐색을 쓰려고 시도했으나 이는 시간복잡도에서 문제가 발생하여 다른 방법을 고안하였다.

 

바위의 위치를 굳이 알아내어 제거하지 않더라도 제거할 바위의 개수를 변수로 두고 해당 변수와 n값을 비교하고 이를 이분탐색에 반영하게 되면 문제를 풀 수 있다는 것을 생각해냈다.

이 코드를 보게 되면 우선 left,right는 distance까지의 범위로 설정해두고, 이에 대한 mid값을 거리의 최솟값으로 두고 문제를 접근한다 이후, for문을 보게 되면 바위 배열에서 초기 바위의 위치의 차 값을 mid(거리의 최솟값)과 비교하여 거리의 최솟값보다 길거나 같으면 해당 바위를 current로 변경하고 min_distance라는 결과값들을 모아 놓은 리스트와 비교하여 최솟값의 여부를 따진다. 이후, 이분탐색의 mid를 설정하는 단계에서는 remove_cnt가 최대 바위를 제거할 수 있는 수인 n보다 클 경우 바위를 너무 많이 제거했으므로 mid를 줄여서 바위를 적게 제거시키고, 그 반대인 경우에는 left=mid+1과 같이 코드를 짜주면 된다.