알고리즘) 2019 카카오 개발자 겨울 인턴십, 징검다리 건너기

2019 카카오 개발자 겨울 인턴십

징검다리 건너기

프로그래머스

풀이

 투 포인터 알고리즘으로 풀다가 효율성 13번만 시간 초과가 뜨길래 이진 탐색으로 풀었다. 이진탐색이기에 left, mid, right를 무엇으로 잡을 것인지가 핵심이다.

 

1. 돌의 stepping 수(=건널 수 있는 사람의 수) 최소값, 최대값을 각각 left, right에 넣어준다.

2. while문을 돌면서 mid 값 (건널 수 있는 사람의 수 예상 답)과 비교하면서 건널 수 있을 경우에는 answer을 저장해주고 최소인 left를 mid+1로 저장한다.

3. 건널 수 없는 경우에는 right를 mid-1로 줄여준다.

4. 답이 나왔다.

 

코드

public class SteppingStones_Kakao2019 {
    private static int solution(int[] stones, int k) {
        return binarySearch(stones, k);
    }

    private static int binarySearch(int[] stones, int k) {
        int left = 200000000;   // stones 최대값을 넣어줌 (다 건너는 상황)
        int right =0;           // 최소값을 넣어줌 (못건너는 상황)
        int answer =0;

        for(int num : stones) {
            left = Math.min(num,left);  // min 값
            right = Math.max(num,right);    // max 값
        }

        while(left <= right) {
            int mid = (left+right)/2;
            if(isPass(stones, mid, k)) {
                left = mid+1;
                answer = mid;
            } else {
                right = mid-1;
            }
        }
        return answer;
    }

    private static boolean isPass(int[] stones, int mid, int k) {
        int prev =-1;   // 처음 땅에서 시작 ~> 돌이 0 IDX 부터 시작하기 떄문
        for(int i=0; i<stones.length; i++) {
            if(i-prev >k) {  // 못건너는 상황에서 k보다 커지면
                return false;
            }
            if(stones[i] >= mid) { // 건널 수 있음
                prev = i;   // 건넘 표시
            }
        }
        return stones.length-prev <= k ? true : false;  // 마지막 돌로 부터 다음 땅까지 건널 수 있는지 검증
    }


    public static void main(String[] args) {
        int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};

        int k =12;

        System.out.println(solution(stones, k));
    }
}