[JS] 징검다리

🔒 문제 (프로그래머스)

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

 

---

 

🔑 해결

🌌 알고리즘 - 이분탐색

distance(입력값)의 크기가 매우 크고 정렬된 데이터(정렬된 rocks) 활용 가능 => 이분탐색

1) 위치 순으로 rocks를 정렬하여 바위 사이의 거리를 계산할 수 있도록 만든다.

2) 이분탐색을 이용하여 left, right을 거리 최소값이 될 수 있는 범위로 잡고, mid로 최소값을 찾는다. 각 바위 사이의 거리가 mid보다 작다면 해당 바위는 제거 가능하다.

• n개까지 제거했음에도 거리가 mid보다 작다면 최소값이 mid 보다 작은 것이므로 right = mid -1로 범위를 줄여 재탐색한다.
• 제거한 바위 개수가 n보다 작거나 같다면 mid가 최소값이거나 그보다 큰 것이므로  left = mid + 1로 범위를 줄여 재탐색 한다.

function solution(distance, rocks, n) {
    let answer = 0;
    let left = 0;
    let right = distance;
    
    rocks.sort((a, b) => a - b);
    
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        let prev = 0;
        let count = 0;
        
        for(let i = 0; i < rocks.length; i++) {
            if(rocks[i] - prev < mid) {
                count++;
                if(count > n) {
                    break;
                }
            } else {
                prev = rocks[i];
            }            
        }
        if(count > n) {
            right = mid - 1;
        } else {
            if(mid > answer) {
                answer = mid;
                left = mid + 1;
            }
        }
    }
    
    return answer;
}

 

 

참고 https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.4-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-JS