프로그래머스 이진탐색 Level 4 (징검다리)

문제

---

출발지점부터 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 이상 바위의 개수 이하입니다.

 

 

 

풀이

---

이진탐색은 항상 기준을 두는 값이 중요하다.

이문제에서는 기준을 거리의 최솟값을 구해야하는 문제기 때문에, 최소거리를 기준으로 문제를 풀어야한다.

 

거리를 기준으로 징검다리를 없애면 n 보다 큰가 작은가, 앞의 글이 핵심 알고리즘이다.

 

밑의 코드는 이진탐색을 하는 코드다.

mid 가 최소거리를 말한다.

while(left <= right){
	mid = (left + right) / 2;
            
	lastRock = 0;
	count = 0;
	for(int i = 0 ; i < rocks.length ; i++){
		//lastRock 으로 지워지지않은 마지막 징검다리의 위치를 저장한다.
		//만약 mid 보다 거리가 크다면 그 때의 징검다리가 지워졌다 생각하고 count++ 을 해준다.
		if(mid > rocks[i] - lastRock){
			count++;
		}
		//아니라면 그때의 위치를 lastRock에 저장한다.
		else{
			lastRock = rocks[i];
		}
	}
	//도착지점 돌과 거리도 비교해준다.
	if(mid > distance - lastRock )
		count++;
            
	//n 보다 count 가 크면 mid를 줄여야한다.
	if(count > n ){
		right = mid - 1;
	}
	// n보다 count 가 작으면 그때의 mid값을 answer 에 저장하고 mid를 늘린다.
	else{
		answer = Math.max(answer, mid);
		left = mid + 1;
	}                     
}

 

 

<전체코드>

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        Arrays.sort(rocks);
        
        int left = 1, right = distance, mid = 0;
        int count = 0;
        int lastRock = 0;
        
        while(left <= right){
            mid = (left + right) / 2;
            
            lastRock = 0;
            count = 0;
            for(int i = 0 ; i < rocks.length ; i++){
                if(mid > rocks[i] - lastRock){
                    count++;
                }
                else{
                    lastRock = rocks[i];
                }
            }
            if(mid > distance - lastRock )
                count++;
            
            if(count > n ){
                right = mid - 1;
            }
            else{
                answer = Math.max(answer, mid);
                left = mid + 1;
            }            
            
        }
        
        return answer;
    }
}