Today's Algorithm(2019-01-27)

programmers. 징검다리

많은 사람이 풀지 않는 문제답게 어렵네요. 어떻게 접근해야할지 몰라 모범답안을 참고하였습니다. 전혀 생각해보지 않은 방법이라 신선하기도 하면서 다음에 또 이렇게 풀 수 있을까 생각하면 확신이 들지 않네요.

 

문제에서 구해야하는 것은 '제거해야할 바위 수가 주어질 때 각 경우의 수에서 각 바위 사이 거리 중 가장 짧은 거리를 구하고 그 중 가장 큰 값'을 구하는 문제였습니다. 모범답안에서 제안하는 문제풀이 방식은 다른 각도에서 생각해보기를 권합니다. '가장 짧을 거리 c일 때 제거해야 할 바위 수 R(c)'로 말이죠. 그렇기 때문에 비교할 때 가장 짧은 거리라고 설정한 값보다 작을 때는 제거해야할 바위수가 +1 증가됩니다. 왜냐하면 가장 짧다고 설정한 값이 맞으려면 돌맹이를 없애 그 사이의 거리를 증가시켜야하기 때문입니다(오름차순으로 정렬했다고 가정).

이 안에는 작은 가정이 하나 있는데요. 제거하는 돌맹이 수가 적을수록 가장 짧은 거리가 작아지고, 제거하는 돌맹이 수가 많을수록 가장 짧은 거리가 커진다는 것입니다. 당연히 돌은 치울수록 그 사이의 거리가 커지기 때문에 당연한 것이죠. 이 사실을 이용하여 이분탐색이 진행됩니다. 문제에서 주어지는 제거해야할 바위 수가 해당 탐색에서 제거해야할 바위 수보다 클 경우 더 제거해야하고 곧 가장 짧은 거리가 커져야함을 말합니다. 그렇기 때문에 이분탐색에서 왼쪽값에 중간값을 넣어 이동시키는 것입니다. 반대로 문제에서 주어진 제거해야할 바위 수가 해당 탐색에서 제거해야할 바위 수보다 적을 때는 덜 제거해야한다는 것이고 즉 가장 짧은 거리가 더 작아져야하기 때문에 오른쪽이 이동되어야 합니다. 그렇게 이분탐색을 통해 가장 최적의 짧은 거리를 찾아갑니다.

 

이렇게 푸는 방식은 문제를 거꾸로 풀고있습니다. 제거해야할 바위수에 따른 가장 짧은 거리를 구하는 것이 아니라 가장 짧은 거리 수에 따른 제거해야할 바위수를 구하는 것이죠. 물론 가정은 위에서 말한바와 같이 제거해야할 바위수와 가장 짧은 거리는 반비례한다는 점을 이용해서요. 코드를 살펴볼게요.

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        Arrays.sort(rocks);

        int a = 0;
        int b = distance;

        while(a < b) {
            int c = (a + b + 1) / 2;

            int p = 0;
            int hits = 0;
            for (int i = 0; i < rocks.length; i++) {
                if(rocks[i] - p < c) {
                    ++hits;
                } else {
                    p = rocks[i];
                }
            }

            if(hits > n) {
                b = c - 1;
            } else {
                a = c;
            }
        }

        return a;
    }
}

이전에 풀던 방식과 달리 여기선 while(a + 1 < b) 가 아니라 while(a < b) 이기 때문에 무한루프를 막기위해서 22줄에서 c-1 를 해주는 과정이 필요합니다.

 

실제 20번째 줄에서 값들을 찍어보면 다음과 같이 나옵니다.

p : 0, hits : 1, a : 0, b: 25, c : 13
p : 0, hits : 2, a : 0, b: 25, c : 13
p : 14, hits : 2, a : 0, b: 25, c : 13
p : 14, hits : 3, a : 0, b: 25, c : 13
p : 14, hits : 4, a : 0, b: 25, c : 13

p : 0, hits : 1, a : 0, b: 12, c : 6
p : 11, hits : 1, a : 0, b: 12, c : 6
p : 11, hits : 2, a : 0, b: 12, c : 6
p : 17, hits : 2, a : 0, b: 12, c : 6
p : 17, hits : 3, a : 0, b: 12, c : 6

p : 0, hits : 1, a : 0, b: 5, c : 3
p : 11, hits : 1, a : 0, b: 5, c : 3
p : 14, hits : 1, a : 0, b: 5, c : 3
p : 17, hits : 1, a : 0, b: 5, c : 3
p : 21, hits : 1, a : 0, b: 5, c : 3

p : 0, hits : 1, a : 3, b: 5, c : 4
p : 11, hits : 1, a : 3, b: 5, c : 4
p : 11, hits : 2, a : 3, b: 5, c : 4
p : 17, hits : 2, a : 3, b: 5, c : 4
p : 21, hits : 2, a : 3, b: 5, c : 4

p : 0, hits : 1, a : 4, b: 5, c : 5
p : 11, hits : 1, a : 4, b: 5, c : 5
p : 11, hits : 2, a : 4, b: 5, c : 5
p : 17, hits : 2, a : 4, b: 5, c : 5
p : 17, hits : 3, a : 4, b: 5, c : 5

 

매번 느끼는 거지면 반복문과 조건문으로 문제를 해결할 수 있다는 점이 참 놀랍습니다.