프로그래머스 - 징검다리 건너기(Java)

파라매트릭 서치(Parametric Search) 문제입니다.

파라매트릭 서치는 최적화 문제를 결정 문제로 바꾸는 이진 탐색 방법입니다.

 

내구도가 깍이는 징검다리가 있을 때와 한 번에 최대로 건널 수 있는 k가 주어졌을 때, 최대 몇명이 건널 수 있는지 구하는 문제입니다.

이 문제를 다시 생각해 보면 다음과 같이 바꿔 이해할 수 있습니다.

'최소와 최대 내구도 사이의 값을 이용해 징검다리의 내구도를 변화시켰을 때 건널 수 있는가?' 입니다.

징검다리의 내구도를 변화시키면서 내구도가 0이 k개 이상 나오면 건널 수 없고, k개 미만으로 나오면 건널 수 있습니다.

이 내구도는 최소와 최대 내구도의 값을 절반씩 바꿔 나가는 이진 탐색을 쓸 수 있습니다.

 

이진 탐색의 시간 복잡도는 O(1)이고, 징검다리의 내구도를 확인 하는 시간 복잡도는 O(N)입니다.

따라서 O(1*N)이기 때문에 O(N)으로 해결할 수 있습니다.

 

[구현 코드]

class Solution {
    public static int solution(int[] stones, int k) {
        int n = stones.length;

        int lo = Integer.MAX_VALUE;
        int hi = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            lo = Math.min(lo, stones[i]);
            hi = Math.max(hi, stones[i]);
        }


        while (lo < hi) {
            // 깍이는 내구도
            int mid = (lo + hi) / 2;

            // mid 만큼 내구도를 깍았을 때, 건널 수 있는지 확인
            if (canCross(stones, k, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    private static boolean canCross(int[] stones, int k, int mid) {
        int cnt = 0;
        for (int i = 0; i < stones.length; i++) {
            if (stones[i] - mid <= 0) cnt++;
            else cnt = 0;

            // 0이 k개 만큼 반복되면 건널 수 없음
            if (cnt == k) return false;
        }
        return true;
    }
}