[프로그래머스] (Java) 징검다리 (이분탐색)

 

📑 1. 문제설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
 

 
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
 
제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

 

---

💡 2. 접근방식

 
시간 복잡도 때문에 브루트 포스로 하면 조합의 갯수가 너무 커져서 안 되고 이분탐색으로 해야 한다.
 
솔직히 이분 탐색을 이 문제에 어떻게 적용할 지 감이 안 잡혀서 다른 블로그를 봤다.
코드를 짜는 것보다 이분탐색을 이 문제에 어떻게 써먹을 지가 너무 어려웠고
그걸 이해하는데 시간이 오래 걸렸다. 
 
감 안잡히시는 분들은 이 블로그 보시면 그림으로 친절하게 설명이 되어 있다.
나도 이거 보고 바로 무슨 말인지 감 잡았다 ㅎㅎㅎㅎ

[프로그래머스] 징검다리-JAVA

 
음.....
 
진짜 진짜 쉽게 설명해보겠다...
 
먼저 rocks를 오름차순 정렬해 준다. 
[2, 11, 14, 17, 21] -> [2, 11, 14, 17, 21]
 
그리구 각 돌 사이의 거리를 담아줄 배열 interval[] 을 선언
rocks에 들어있는 바위 사이의 거리를 계산 해서 담아준다.
돌이 0부터 25 사이에 놓아져 있으니까 interval크기는 rocks.length+1 로 해 준다

0~2	2~11	11~14	14~17	17~21	21~5
2	9	3	3	4	4

 
고로 interval은 [2, 9, 3, 3, 4, 4]
 
일단 mid라는 값은 
정답이 될 수 있는 후보
라고 생각하면 편하다. 
 
mid 값을 임의로 설정 해 주면서 이진 탐색을 하는건데 이 mid 값에 따라 돌을 제거 할 수 있는지 확인하는 것이다.
interval 요소를 sum에 하나씩 누적 해 주면서 이 값이 mid 값보다 작으면 돌을 제거해서 구간을 합쳐 준다.
그리고 제거한 돌의 수가 n보다 큰지 확인한다. 
n보다 크면 돌이 너무 많이 제거됬기 때문에 탐색 구간을 왼쪽으로 좁혀 주고,
그렇지 않으면 제거 해야 하는 돌보다 더 많은 돌이 제거되었기 때문에 구간을 오른쪽으로 설정한다. 
 
그니까 이진탐색 수행하는 동안 while 문 안에 조건이 두개라고 생각하면 간단하다.
 
첫번째로 비교할 조건은 mid랑 구간 거리들의 합 sum
=> 돌을 제거할 지 말지 결정포인트
 
두번째로 비교할 조건은 제거된 바위의 수와 제거해야 할 바위의수 n 
=> 탐색 구간을 왼쪽으로 할 지 오른쪽으로 할 지 결정포인트
 
자, interval 이 [2, 9, 3, 3, 4, 4] 일때
처음에는 mid = ( 1 + 25 ) / 2 니까 13이다.
 
interval[0] = 2 < 13, 바위 제거
interval[0] + interval[1] = 2 + 9 = 11 < 13, 바위 제거
interval[0] + interval[1] + interval[2] = 2 + 9 + 3 = 14 < 13
바위제거 안하고 거리 합을 0으로 초기화 해준다.
 
그리고 Interval[3] = 3 < 13, 바위 제거
interval[3] + interval[4] = 3 + 4 = 7 < 13, 바위 제거
interval[3] + interval[4] + interval[5] = 3 + 4 + 4 = 11 < 13바위 제거
 
여기까지 제거한 바위수 5인데 문제에서 제거해야 할 바위 수 2이다.
문제에서 제거한 바위 수가 너무 많기 때문에 mid = 13은 너무 큰 값이라는 것이다. 
따라서 거리를 왼쪽으로 좁혀도 됨 ㅎㅎㅎㅎ right = mid - 1 로 설정해 줘서 right는 12가 된다.
 
이렇게 계속 반복을 해 주면 된다.
이해하면 정말 쉬운 문제이지만 이해하기 전까지는 생각을 오래 해야 한다~ 
 

---

⭐ 3. 코드

첫번째 시도 틀림

 
아... 또? 분명히 제대로 했는데 어디가 잘못됐나
실행 결과가 13이라고 오바인데 ^^;;;
 
처음에 interval[] 초기화 잘못했다.
바위 사이의 거리를 담아야 하는데 그냥 생각 없이 쓰다가 바위 위치 그대로 담음^^

for(int i = 1; i < rocks.length; i++) {
    interval[i] = rocks[i];
}

for(int i = 1; i < rocks.length; i++) {
    interval[i] = rocks[i] - rocks[i - 1];
}

 
 
정답코드

import java.util.*;

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

주석 달기가 귀찮다..
그리고 intervals로 할걸 그냥 interval로 했네요
변수명 sumd는 sumDistance 하려다가 너무 길어서 줄였습니다~
 
처음에는 쓰면서 조건문 위치가 헷갈렸다. while 문 안에 for문은 돌 제거하는 로직이고, for 문과 별개로 있는 if 문이 제거된 바위 수과 제거할 바위수를 비교하는 이분탐색 로직이다. 그리고 또 removedRocks가 n보다 큰 경우에만 탐색 범위값을 왼쪽으로 옮겨주는 것이고 만약 제거된 바위 = 제거해야 하는 바위 수가 같아졌다?
 
그 값이 같은 경우에도 오른쪽으로 한번 더 탐색해 줘야 한다. (더 큰 값 있을 수도 있으니까) 

---

👉🏻 4. 같은 유형 문제(이진탐색)

[프로그래머스] (Java) 입국심사 문제풀이 (이분탐색)