징검다리

[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다. 우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다. 제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다. 처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다. 그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. ..