오늘도 어제 풀었지만 하루 미룬 포스팅임니도 ~~
이번 문제는 프로그래머스 고득점 kit 이분탐색 분류에 있는 level4 문제입니다 ! 이분탐색 문제는 다 재밌는 고 같다.. 알골 문제풀이 레포 보니까 첫 level4 문제던데.. 어렵지만 꿀잼문제.. 다들 풀어보세요 ~~
https://programmers.co.kr/learn/courses/30/lessons/43236
고득점 kit 이분탐색 ✅ 끄으읕 !!! 드디어 다 푼 카테고리가 나오다니.. ( 이분 탐색 두 문제임; ㅎ; ) 분발해서 얼른 고득점 kit 다 뿌순다아 !
문제 설명
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
| 제거한 바위의 위치 | 각 바위 사이의 거리 | 거리의 최솟값 |
|---|---|---|
| [21, 17] | [2, 9, 3, 11] | 2 |
| [2, 21] | [11, 3, 3, 8] | 3 |
| [2, 11] | [14, 3, 4, 4] | 3 |
| [11, 21] | [2, 12, 3, 8] | 2 |
| [2, 14] | [11, 6, 4, 4] | 4 |
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
제한 사항
- 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.
입출력 예
| distance | rocks | n | return |
|---|---|---|---|
| 25 | [2, 14, 11, 21, 17] | 2 | 4 |
풀이 방법
level4답게 어려운 문제 ! 이분탐색 카테고리에 있지 않아서 어떤 알고리즘으로 풀어야하는지 힌트를 얻지 못 했으면 문제만 읽고서 이분탐색으로 풀어야겠다는 생각을 못 했을 거 같다. ( 제한 조건에서 distance 범위가 1,000,000,000인 것이 살짝 이분탐색의 감이 오긴 하지만..! )
문제를 처음 읽었을 때, 바위들을 정렬하고서 각 간격들을 구해냈다. 후에 이 중에서 제일 작은 값들을 n개만큼 제거해 나가야 한다고 생각했다. 어떻게 제거할 수 있을까 고민하면서 왜 이분탐색일까를 고민하게 되었다. 과연 이분탐색 해야하는 대상이 뭘까..? 하는 고민 !
이분탐색을 하려면 정렬되어 있어야 하고, 시작-끝 범위가 분명해야 한다는 것을 생각하며 그러한 대상을 고민하다가 바위인가..? 라는 생각으로 바위에서 어떻게 이분탐색을 통해 원하는 값을 도출할 수 있을까 고민하게 되었다. 결국 해답을 찾지 못하고 다시 처음부터 접근해보기로 하였다.
지금 내가 구해야하는 값은 바위 사이의 간격이다. 바위 사이의 간격들 중에서 n개를 제거했을 때 제일 작은 간격이 제일 큰..! ( 아니 뭐래 말이 왜이래ㅋㅋㅋㅋㅋㅋ ) 이 때, 구해야하는 값인 바위들 사이의 간격은 1-distance사이로 범위가 한정되어 있다. 여기서 힌트를 얻어 이분탐색 해야하는 대상은 바위 사이의 간격이고 1-distance사이에서 이분탐색을 진행하면 된다는 생각을 하게 되었다.
그렇다면 이것을 코드에 옮기기 위해서 이분탐색을 하면서 left-mid 구간을 선택할지 mid-right 구간을 선택할지 고르는 기준은 무엇일까?를 고민하게 되었다. 결국은 구해야하는 x라는 값에 이분적으로..? 가까워지기 위함을 목적으로 하는 것인데.. 문제에서 x라는 값을 판별하는 조건은 바위 n개를 제거해서 바위 사이의 간격 중 제일 작은 값을 x로 만들 수 있는가이다. 이걸 코드로 어떻게 작성하지 고민하면서 거꾸로 바위 사이의 간격 중 제일 작은 값이 x가 되려면 몇 개의 바위를 제거해야 하는가 ! 를 조건으로 한다면 제거해야 하는 바위의 수를 입력받은 n과 비교하여 이분탐색에서의 조건을 정할 수 있을 것 같았다.
위의 기나긴 사고의 과정을 거쳐 정리한 알고리즘으로 입출력 예에 대해서 먼저 아래의 그림과 같이 손으로 순차적으로 이분 탐색을 진행하면서 오류는 없는지 코드로 옮기는 과정에 있어서 어떠한 변수가 필요하고 조건은 정확이 어떻게 작성하면 될지 정해나갔다.
+) 문제를 풀고서 다른 사람들의 코드를 보면서 mid를 이용해 left or right를 재설정 할 때에 +1, -1을 해준다면 while의 조건을 > 1이 아닌 > 0 or left > right와 같이 더 명확하게 지정해줄 수 있다는 걸 깨달았다. 이분탐색에서 원래 보통 mid+1 mid-1로 지정을 해주는데 위와 같이 손으로 그리며 알고리즘을 구상할 때 이를 깜빡한 것이다 !
코드
import java.util.Arrays;
class Solution {
public int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks);
int[] subDistances = new int[rocks.length+1];
subDistances[0]=rocks[0];
subDistances[rocks.length]=distance-rocks[rocks.length-1];
for(int i=1; i<rocks.length; i++) subDistances[i] = rocks[i]-rocks[i-1];
int left = 1;
int right = distance;
int mid = (left+right)/2;
int current, removed;
while(right-left > 1){
removed = 0;
current = 0;
for(int i=0; i< subDistances.length; i++){
current += subDistances[i];
if(current < mid) removed++;
else current = 0;
}
if(removed > n) right = mid;
else left = mid;
mid = (left+right)/2;
}
return mid;
}
}