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

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

프로그래머스

 

 

풀이 유형

• 이분탐색
• 슬라이딩 윈도우

 

풀이

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        int st = 1, en = 200000000;
        
        while(st <= en) {
            int mid = st + (en - st) / 2;
            
            int max = 0;
            int len = 1;
            for(int i = 0; i < stones.length; i++) {
                if (stones[i] <= mid) {
                    len++;
                }
                
                else {
                    len = 1;
                }
                max = Math.max(max, len);
            }
            System.out.println("mid: " + mid + " max: " + max);

            if (max <= k) {
                st = mid + 1;
            }
            
            else {
                en = mid - 1;
            }
            
        }
        
        return st;
    }
}

 

 

회고

 

처음엔 매 시간이 지날때마다 돌의 값을 1씩 줄여주고, 이 때 건너갈 수 없는 경우를 체크하는 로직을 생각했다.

 

하지만, 매번 돌의 값을 갱신해주는것은 O(n)이 들고, 이 작업을 돌의 길이만큼 반복해줘야 하므로 O(N^2)이 걸린다. 문제에서 주어진 제한 길이는 20만이기 때문에 제한시간을 넘어갈 것이다.

 

그래서 이분탐색의 풀이를 떠올렸는데, 어떤 식으로 돌의 값과 비교해야할지 감이 오지 않았다.

 

 

해당 돌의 초기 값들이다. 어떻게 하면, 한번에 건너뛰는 값이 k이하인지 판단할 수 있을까?

 

이분탐색의 시작값을 0으로 잡고, 끝 값을 돌의 최댓값인 2억으로 잡았다.

이때, mid값은 중간값이므로 이때 돌을 순회하며 값을 비교한다.

 

돌의 값이 mid보다 작다면, cnt를 증가시켜주고 mid보다 크다면, cnt를 1로 초기화 시켜준다. 이 때 초기화 시켜주는 이유는 연속되지 않고 다시 그 지점부터 시작하기 때문이다.

 

이 때, cnt의 max값과 k를 비교해준다.

if (max <= k) {
    st = mid + 1;
}

else {
    en = mid - 1;
}

 

max값이 k보다 크다면, 상한점을 낮춰줘야 하고 같거나 작다면 하한점을 높여줘야 한다.

 

 

처음에 mid값은 1억이고, 이 때 돌의 값과 비교하면 당연히 모든 돌이 1억보다 작다! 그렇기 때문에 cnt는 돌의 총 갯수 + 1이 될 것이다.

(여기서 +1을 하는 이유는 길이는 항상 1이기 때문이다.)

이렇게 쭉 이분탐색을 진행하다가, max가 3이 되는 시점이 온다. 

 

이때, cnt의 값은 4이기 때문에 3보다 크다. 그렇기 때문에 상한점을 높여서 다시 탐색해줘야 한다

 

문제에서 주어진 실패 케이스인데 딱 위와 값만 다를뿐 똑같은 것을 확인할 수 있다.

 

 

이렇게 진행하며 max <= k인 최초의 st, 시작점을 리턴해주면 된다.