2019 카카오 개발자 겨울 인턴십(징검다리 건너기) - Java

[징검다리 건너기]

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

프로그래머스

 

 

* 로직

• 이분 탐색을 이용한다
  
  
• front = 0, rear = 최댓값으로 초기화한다
• 징검 다리를 건널 수 있는 사람의 수를 mid로 설정한다
• mid를 기준으로 stones 배열을 차례대로 탐색한다
  • 만약 stones[i] - (mid-1) <= 0 이라면 -> 카운팅을 진행한다
  • 만약 stones[i] - (mid-1) > 0 이라면 -> 카운팅을 0으로 초기화한다
  • 만약 카운팅 횟수 >= k 라면 -> 더이상 도약이 불가능하다(false)
• 위의 mid값을 기준으로 징검다리를 건널 수 있다면 더 많은 사람들이 건널 수 있는지 탐색
  • front = mid + 1
• 건널 수 없다면, 건널 수 있는 사람의 수(mid)를 줄여준다
  • rear = mid - 1
• front <= rear까지 반복하고, 끝난다면 답을 출력한다

 

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;

        int front = 0;
        int rear = Integer.MAX_VALUE;
        while (front <= rear) {
            int mid = (front + rear) / 2;   // 가능한 사람의 수

            // 해당 mid의 수가 가능하다면 -> 더 많은 사람이 가능한지 탐색
            if(isPossible(mid, stones, k)) {
                answer = mid;
                front = mid + 1;
            }

            // 불가능하다면 -> 가능한 사람의 수를 줄이기 위해 탐색
            else rear = mid - 1;
        }

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

            // 못건너는 돌의 연속하는 개수가 k개가 된다면 불가능
            if(cnt >= k) return false;
        }

        return true;
    }
}