[프로그래머스 (Java)] 징검다리

https://programmers.co.kr/learn/courses/30/lessons/43236?language=java 

코딩테스트 연습 - 징검다리

[프로그래머스: 코딩테스트 연습 고득점 kit] 의 이분탐색의 두번째 문제입니다.

이분탐색에서는  start, end 값을 어떻게 정의할 것인가, 어떤 기준으로 mid 와 start/end 를 바꿔나갈 것인가  가 쟁점입니다.

1. start = 1, end = distance 로 시작합니다.
2. mid = (start + end) / 2 + 1 로 지정하고, mid = answer 일때, 최소 몇개의 돌을 옮겨야 하는지(neededRocks)를 계산합니다.
3. 만약 neededRocks 가 n 보다 크다면, answer = mid 인 mid 값을 줄여아한다는 것을 의미합니다. 따라서 end = mid - 1 로 업데이트 합니다.
4. 만약 neededRocks 가 n 이하라면, answer >= mid 가 될 것입니다. 따라서 start = mid 로 업데이트 합니다.

 

start / end 를 초기화하는 것과 neededRocks 를 결정하는 부분까지는 크게 어렵지 않지만

start 와 end 를 업데이트 하는부분이 까다롭기 때문에 부연해보려고 합니다.

neededRocks 는 mid 가 설정되었을때 mid 값이 answer 로 적당한지 판단하는데 사용됩니다. 

 

---

추가 설명

1) neededRocks > n 인 경우

answer이 mid가 되기 위하여 제거해야하는 돌들이 n 보다 많다는 것을 의미하고 이는 실제 answer 이 mid 보다 작다는 것을 의미합니다.

따라서 end = mid 를 넣어서 답을 좁혀나가야 하고 end = mid -1 을 넣어 업데이트 합니다 

여기서 mid 가 아닌 mid - 1 로 업데이트 하는 이유는 answer 이 mid 보다 작기 때문입니다. 만약 answer 이 mid 이하의 값을 가질 수 있다면 mid - 1 이 아닌 mid 값으로 end 를 업데이트 해야합니다.

 

2) neededRocks <= n 인 경우

answer이 mid가 되기 위하여 제거해야하는 돌들이 n 보다 작거나 같다는 것을 의미하고, 이는 실제 answer 이 mid 와 같거나 크다는 것을 의미합니다.

따라서 start 값을 키워서 답을 좁혀나가야 하고 start = mid 를 넣어 업데이트 합니다.

start 에 mid + 1 을 넣지 않는 이유는 start 가 mid 와 같은 경우도 고려해야 하기 때문입니다.

 

3) mid = (start + end) / 2 + 1

mid 에 (start + end) / 2 와 (start + end) / 2 + 1 중 어떤 값을 넣어야 하는지는 1)과 2)에 의해 결정됩니다.

end = mid -1 / start = mid 로 설정했다면, 다음과 같은 경우를 생각해 볼 수 있습니다. 

 

(example) start = 7, end = 8, 실제 정답 7 인 상황을 생각해보면

mid 에 (start + end) / 2 를 넣어서는 while  loop 가 끝나지 않습니다. 

이유는 end  = mid -1 / start = mid 로 업데이트 하기 때문입니다. end 가 줄어들어 start = end = 7 로 이분탐색이 마무리 되기 위해서는 mid 에 (start  + end) / 2 + 1 이 들어가야합니다.

 

이분 탐색에서 가장 중요한 부분이자 가장 어려운 부분은 start 와 end 값을 어떤 기준으로 어떤 값으로 업데이트 할지 결정하는 일입니다. 

큰틀에서는 다음과 같이 결정할 수 있습니다.

1. 답이 줄어들어야 한다면 end 를 업데이트 한다

2. 답이 늘어나야 한다면 start 를 업데이트 한다. 

 

또한 start / end 를 업데이트 할때 mid / mid+1 / mid-1 중 어떤 값을 넣어야 하는지는 

start / end 가 mid 에 비교했을때 이상/이하 인가 아니면 초과/미만 인가에 의해 결정됩니다.

 

해당 문제를 정리하면 다음과 같습니다.

answer = mid 일때 치워야 하는 돌의 개수가  n 보다 큼 → 답이 줄어들어야 한다 → 또한 답은 mid 미만이다 → end = mid - 1

answer = mid 일때 치워야 하는 돌의 개수가 n 보다 작음 → 답이 늘어야한다. → 또한 답은 mid 이상이다 → start = mid

 

end = mid - 1 / start = mid 를 넣기 때문에 mid = (start + end) / 2 + 1 이 돼야 한다.

이를 코드로 구현하면 다음과 같습니다.

---

import java.util.Arrays;

public class Solution {
    public int solution(int distance, int[] rocks, int n) {
        // 출발점과 도착점을 넣어서 새로운 배열 생성
        int[] newRocks = new int[rocks.length + 2];
        newRocks[0] = 0;
        newRocks[rocks.length + 1] = distance;
        for (int i = 0; i < rocks.length; i++) {
            newRocks[i + 1] = rocks[i];
        }
        Arrays.sort(newRocks);

        // start, end 값 조정
        int start = 1;
        int end = distance;

        while (start < end) {
            // mid 값 정의
            int mid = (start + end) / 2 + 1;

            // answer = mid 일 때 치워야하는 최소 돌의 개수
            int neededRocks = 0;

            // rocks[i] < 돌 < rocks[i] + mid 사이에 있는 돌을 치움
            for (int i = 0; i < newRocks.length; i++) {
                for (int j = i + 1; j < newRocks.length; j++) {
                    if (newRocks[j] >= newRocks[i] + mid) {
                        // 돌 안치워도됨
                        i = j - 1;
                        break;
                    } else {
                        // 돌을 치워야함
                        neededRocks++;
                    }
                }
            }

            // answer = mid 일때 치워야하는 돌의 개수가 오버된다
            if (neededRocks > n) {
                end = mid - 1;
            // answer = mid 일때 치워야하는 돌의 개수가 n 이하인 경우
            } else {
                start = mid;
            }
        }
        int answer = start;
        return answer;
    }
}