[프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🔗 문제 링크

[프로그래머스] 징검다리 건너기 / 2019 카카오 개발자 겨울 인턴십

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

 

📝 풀이 과정

돌의 최솟값을 기준으로 이분탐색하는 방법을 사용했다. 범위는 돌의 크기인 1 ~ 200,000,000으로 지정해주었다.

 

N-1번 니니즈까지 길을 건넜다고 가정하고 N번째 니니즈가 길을 건너는 차례라고 생각한다. K번 이내의 거리에 N이상의 값이 존재해야 길을 건널 수 있기 때문에 N미만의 값이 연속적으로 k개 이상 나온다면 길을 N번은 건널 수 없다는 의미가 된다.

 

따라서 범위를 줄여주고 다시 탐색을 시작해주고, 만약 연속 값이 k보다 작다면 길을 건널 수 있는 경우로 값을 저장한 값을 늘려 다시 탐색을 진행하였다.

 

⏱ 시간 복잡도

이분탐색의 시간 복잡도는 $O(\log({2\times 10^8}))$이다.

탐색할 때마다 선형으로 돌을 탐색해야 하기 때문에 최종 시간 복잡도는 $O(n\times\log({2\times10^8}))$

 

💻 코드

public class Solution {
    public int solution(int[] stones, int k) {
        int start = 1, end = (int) (2 * 1e8), ans = 0;

        while (start <= end) {
            int mid = (start + end) / 2;

            int cnt = 0;
            int max = 0;
            for (int stone : stones)
                max = Math.max(max, cnt = (stone < mid ? cnt + 1 : 0));

            if (max >= k) {
                end = mid - 1;
            } else {
                ans = mid;
                start = mid + 1;
            }
        }
        return ans;
    }
}