[JAVA] 징검 다리(코딩테스트 고득점 Kit [이분 탐색]) - LEVEL4

📂문제 설명

 

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

 

---

📂아이디어 및 알고리즘(문제 풀이) 

• 문제 접근
  • 구하고자 하는 return 값은 어떠한 distance값일때 최솟값중 가장 큰 값을 찾는 문제이기 때문에 이분 탐색 문제임을 알 수 있었다.
  • 중요한건 N개의 돌을 제거하고 그 사이의 거리가 최대일 때를 찾는 것이다.
  • 그럼 돌을 어떻게 제거하면서 그 거리를 찾을래? 
  • 이분탐색의 left와 right를 distance로 잡고 구하고자 하는 distance를 기준으로 돌을 제거했을때 비교를 해준다.
  • 돌을 제거하기 위해서 꼭 이전 돌의 값을 기억해 두면서 비교해 나간다.  
• 문제 풀이
  • while문에서 for문을 보게되면 돌과 돌사이 거리에 따라 제거해나가는 로직을 구현하였다.
  • if(rocks[i]-preRock) < mid 
    • i를 순회하면서 돌과 돌사이 거리를 계산하여 mid 보다 작으면 돌을 더 제거하여 거리 값을 늘린다.
  • 그렇게 돌과 돌사이 거리값이 mid보다 커지면 더이상 순회의 의미가 없어지므로 preRock값을 rocks[현재 index]값으로 넣고 다시 순회한다.
  • 이렇게 하면 돌과 돌사이 거리가 mid보다 커져야만 다음 돌과 돌 사이를 측정하게 되고 이때 제거되어 있는 돌 수를 비교하여 left값과 right값을 조정한다.
  • remove값이 N보다 커지면 돌을 너무 많이 제거했다는 의미이고 mid값이 너무 크기 때문에 돌을 더 제거했다는 의미가 되기때문에 mid값을 낮추기 위해 right값을 낮춰준다.
  • 반대로 N보다 같거나 작으면 일단 answer값으로 mid값과 비교하여 더 큰 값을 넣어주고 left값을 증가시켜준다.
  • 돌을 더 제거해야하기 때문에 left값을 올려서 mid값을 올려준다.  

 

 

📂소스 코드

import java.util.Arrays;
class Solution {
    public static int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        
        int left =1;
        int right=distance;
        
        while(left<=right) {
        	int mid = (left + right)/2;
        	int preRock=0;
        	int remove=0;
        	for(int i=0;i<rocks.length;i++) {
        		if(rocks[i]-preRock < mid) { //현재 돌 - 전 돌 = 돌사이 거리 가 mid보다 큰지 체크
        			remove++;
        			if(remove > n) {
        				break;
        			}
        		}else { //바위 사이의 거리가 mid보다 크면 
        			preRock = rocks[i]; 
        		}
        	}
        	if(remove > n) {
        		right = mid-1;
        	}else {
        		answer= answer>mid ? answer : mid;
        		left = mid+1;
        	}
        }
        return answer;
    }
}