프로그래머스_징검다리<Java>

처음 문제를 접했을 땐, 조합을 떠올렸지만 50,000개 중 2개를 뽑는 경우의 수에는  20억번의 연산이 포함되므로, 효율성 측면에서 낮다고 판단하였다. 그렇다면 시간 효율성을 높일 수 있는 방안 중 어떤 것이 있을까 고민하던 중,하나씩 빼면서 탐색을 하는 것 자체가 모든 경우를 조사해야하는 경우를 포함하므로 거꾸로, 최대가 되는 거리를 미리 정해서 이진 탐색을 활용하여 해당 거리를 줄여나가는 방식으로 문제를 해결하였다.

 

제한 사항에 변수가 1억 이상으로 나와있다면, 시간 효율성을 고려한 알고리즘을 항상 고려해야한다.

1억개 이상의 크기를 갖는 배열을 만들어 이를 숫자별로 만든다면 시간 효율성은 떨어질 수 밖에 없다.

 

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {        
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        int answer = distance;
        
        while(left <= right){
            int mid = (left + right) / 2;
            int removedRocks = 0;
            int prev = 0; //이전 바위의 위치
            
            for(int rock : rocks){
                if(rock - prev < mid){
                    removedRocks++;
                } else {
                    prev = rock;
                }
            }
            
            if(distance - prev < mid){
                removedRocks++;
            }
            
            
            if(removedRocks > n){
                right = mid - 1; //빼낸 바위의 수가 더 많으므로 거리를 더 줄여도 괜찮다
            } else {
                answer = mid; // n보다 작거나 같은 경우도 answer에 후보가 될 수 있다 이는 뒤에서 자세히 설명하겠다.
                left = mid + 1;
            }
    }
        return answer;
    
    }
}

 

왜 제거된 바위의 값보다 작은 경우도 답의 후보인가?

해당 문제는 모든 거리에 대한 완전탐색을 수행하는 것이 아니다. 단지 이전 바위와의 거리만을 비교하며 바위 더 제거할 지를 결정한다. 바위를 제거할 경우 거리는 바위 간 거리는 반드시 증가한다.'

만약 removedRocks <= n이면

• 정확히 n개를 사용하지 않더라도, 나머지 바위는 추가로 제거해서 n개를 맞출 수 있습니다.
• 이때의 mid가 현재까지의 가능한 최소 거리가 됩니다.