[2019 카카오 인턴십]징검다리 건너기

📍 문제 설명

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

프로그래머스

 

💡 접근

전형적인 이분 탐색 문제였다.

1. 건널 수 있는 경우에는 건널 수 있는 인원 수 누적해가면서 인원 수를 높여본다.

2. 건널 수 없는 경우에는 인원 수를 낮춰본다.

건널 수 있는지의 여부는 연속된 디딤돌이 k개가 되지 않을 때이다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    public int solution(int[] stones, int k) {
        int answer = 0;
        //1 ~ 200,000,000 까지 건널 수 있는 경우와 못 건너는 경우를 나눠서 이분 탐색
        int lt = 1;
        int rt = 200000000;
        //건너려고 하는 인원 수
        int mid = (lt+rt)/2;

        while(lt <= rt) {
            //건널 수 있으면 인원 수를 더 높여보기
            if(possible(stones, k, mid)) {
                answer = mid;
                lt = mid + 1;
            }
            //건널 수 없으면 인원 수를 더 낮춰보기
            else rt = mid - 1;

            mid = (lt+rt)/2;
        }
        return answer;
    }

    private boolean possible(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;
            if(cnt == k) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
        int k = 3;

        main.solution(stones, k);
    }
}