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

문제 설명

출발지점부터 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

 

---

 

문제 접근

1. 바위사이의 거리를 구한 뒤, 거리의 최솟값을 보고 n개의 바위를 지우는방식으로 접근하하였습니다.
   
   •  해당 거리의 바위를 지울때 거리기준으로 왼쪽 바위를 지울지 오른쪽 바위를 지울지 비교하여 작은값을 제거.
2. 이진탐색사용. 바위간의 거리 최솟값들 중 최댓값(answer)을 x로 두고 x를 기준으로 바위를 제거.
   
   • x를 기준으로 바위를 지울 때, n보다 지운바위의 갯수가 많으면 x값이 너무 큰 것(x값이 너무 커 바위들을 많이 지움)  
   • x를 기준으로 바위를 지울 때, n보다 지운바위의 갯수가 적거나 같다면 answer의 조건을 충족할가능성이있음.
     • x를 기준으로 했기때문에 n보다 적거나 같게 바위를 지우는 경우는 x보다 더 큰 x값이 존재 할 수 있음. 

 

문제접근1 의 문제점.

거리기준 왼쪽 바위와 오른쪽 바위 중 무얼 없애는지 결정하는 과정에 당장의 현재상태를 보고 판단하는데, 이게 항상 최적일 수는 없기때문입니다.

반례) 16,  [4,8,11],  2

답: 8

문제접근1 방식의 답: 5

 

 

문제 접근2 의 방식에서 기준이 될 값을 무엇으로 정하는지 어려웠지만, 기준을 정하고 나서의 풀이는 간단하였습니다.

[이하 x를 mid로 부르겠습니다.]

 

 

반복문을 돌며

• (현재바위 - 이전바위) < mid 라면 바위를 지워줍니다. ( 이전바위 위치는 바위를 지웠기때문에 변하지않습니다.)
• 반대의 경우에는 '이전바위' 위치를 최신화 합니다. 바위를 지우지 않았기 때문에 다음 바위와의 거리를 재기위해서.

위의 방식을 토대로 이진탐색을 합니다.

 

if(removeCnt>n){break;}

지운바위의 갯수가 n보다 크다면 더 이상 반복문을 돌 필요가 없기때문에 반복문을 빠져나옵니다.

 

answer=answer>mid? answer:mid;

최솟값들중 최대값을 구하기위해 기존의 answer보다 mid값이 크다면 answer값을 최신화 합니다.

public int BinarySearch(int distance, int[] rocks, int n){
	int answer=0;
    Arrays.sort(rocks);
    int left=0;
    int right=distance;
    int mid=0;
    while (left<=right){
    	mid=(left+right)/2;
    	int prv=0;
    	int removeCnt=0;
    	for(int i=0; i<rocks.length; i++){
    		if(rocks[i]-prv < mid){ removeCnt++; if(removeCnt>n){break;}}
    		else{ prv=rocks[i]; }
    	}
        if(removeCnt>n){right=mid-1;}
    	else{answer=answer>mid? answer:mid; left=mid+1;}
    }
    return answer;
}

 

깃허브: https://github.com/jsh9057/Algorithm/blob/master/src/BinarySearch/SteppingStones.java