> 문제
문제 : [징검다리]
> 문제풀이
바위를 n개 만큼 제거한 후 바위 사이의 거리가 최솟값 중에 최댓값을 구하는 문제이다.
말이 좀 어려운데..
반대로 생각하여, 바위 사이의 거리를 가중치로, 바위를 최대한(n보다 같거나 작을 때) 제거할 수 있는 값 중 최솟값을 구하였다.
소스는 다음과 같다.
package level4;
import java.util.*;
public class Solution_징검다리 {
public static void main(String[] args) {
System.out.println(solution(25, new int[] { 2, 14, 11, 21, 17 }, 2)); // 4
System.out.println(solution(100, new int[] { 79, 80, 81, 82, 83 }, 1)); // 1
System.out.println(solution(100, new int[] { 79, 80, 81, 82, 83 }, 2)); // 2
System.out.println(solution(100, new int[] { 79, 80, 81, 82, 83 }, 3)); // 4
System.out.println(solution(100, new int[] { 79, 80, 81, 82, 83 }, 4)); // 21
System.out.println(solution(10, new int[] { 6, 7, 8, 9 }, 3)); // 4
System.out.println(solution(34, new int[] { 5, 19, 28 }, 2)); // 15
System.out.println(solution(16, new int[] { 4, 8, 11 }, 2)); // 8
}
static public int solution(int distance, int[] rocks, int n) {
Arrays.sort(rocks);
int left = 0, right = distance, mid;
while(left <= right){
mid = (left + right) / 2;
int cnt = 0;
int prev = 0;
for(int i=0; i<rocks.length; i++){
if(rocks[i] - prev < mid){
cnt++;
}else prev = rocks[i];
}
if(distance - prev < mid) cnt++;
if(cnt <= n){
left = mid + 1;
}else right = mid - 1;
}
return left-1;
}
}
문제 출처 : Programmers
PREVIOUS[프로그래머스] Level3 - 풍선 터트리기