[프로그래머스] 징검다리 건너기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/64062

문제 풀이

• 초기 접근은 배열의 최솟값을 전체에 빼주고 연속된 0의 갯수를 판별하여 가능 여부를 판별하였는데
  이 방법은 최악의 경우 20만 x 20만으로 시간 초과가 발생한다.
• 이분 탐색으로 풀이하였으며 이분 탐색의 인사이트는 다음과 같다.

  • 각 돌에 적혀있는 내구도를 이분탐색의 범위로 잡는다
  • 이분 탐색의 분기 판별은 mid값이 정해졌을 때 각 징검다리의 돌 내구도에서 mid를 빼주고 징검다리를 건널 수 있는지 여부로 판별하였다.
  • 이 때 건너기 불가능한 최소 mid값이 결과값이 된다. (upper bound)
  • 시간 복잡도는 O(N * logM) (N: 징검다리 돌 갯수, M: 내구도 범위)

소스 코드 (JAVA)

class Solution {
    public int minValue, maxValue;
    public int INF = 987654321;

    public int solution(int[] stones, int k) {
        minValue = INF;
        maxValue = -1;
        for (int stone : stones) {
            minValue = Math.min(minValue, stone);
            maxValue = Math.max(maxValue, stone);
        }

        //이분 탐색
        int low = minValue - 1;
        int high = maxValue + 1;
        while (low + 1 < high) {
            int mid = (low + high) / 2;

            //가능 여부 판별
            boolean stopFlag = false;
            int cnt = 0;
            for (int stone : stones) {
                if (stone - mid <= 0) {
                    if (++cnt == k)
                        stopFlag = true;
                } else 
                    cnt = 0;
            }
            
            if (stopFlag) high = mid;
            else low = mid;
        }
        return high;
    }
}