[Java] 프로그래머스 - 징검다리 건너기

[문제]

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

프로그래머스

[풀이]

단순히 친구를 한명씩 징검다리를 건너는 방식으로 풀이를 진행해보니, 정확성은 통과하였지만 효율성에서 걸렸습니다.

시간을 단축시켜 보기 위해 최소값 min을 구해, 1칸씩 이동할 수 있는 친구들을 건넌후, 나머지를 건너게 해보았지만 역시나 효율성에서 통과하지 못해 풀이를 참고하였습니다.

 

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

풀이를 찾아본 결과 이진탐색으로 풀이하는 문제였습니다.

 

예를 들어, [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 가 주어졌다면 최소값 left는 1, 최대값 right는 5로 세팅됩니다.

while문을 통해 이진탐색을 진행하는데, mid = (right + left)/2 가 되고 각 mid마다 cross()를 통해 해당 mid 값으로 건널수 있는지 확인하며 mid를 갱신해줍니다.

 

만약 mid로 건널 수 있다면 mid보다 작은 값으론 모두 건널수 있으므로 left = mid + 1을, mid로 건널수 없다면 해당 mid보다 큰값으로는 건널 수 없다는 뜻이므로 right = mid -1 로 갱신해주었습니다.

 

1) mid = 3  -> 건널 수 있음 -> left =4로 갱신

2) mid = 4 -> 건널 수 없음 -> right = 3으로 갱신

3) left > right 이므로 이분탐색 종료

 

이러한 과정을 거치고 나면 right에 가능한 최대값이 들어가게 됩니다.

 

[코드]

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        // 가장 작은 값 찾기
        int left = stones[0];
        int right = stones[0];
        for(int i=1;i<stones.length;i++) {
            if(left > stones[i]) {
                left = stones[i];
            }
            if(right < stones[i]) {
                right = stones[i];
            }
        }
    
        // 이분탐색
        while(left <= right) {
            int mid = (left + right)/2;
            if(cross(stones, k, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        answer = right;
        return answer;
    }
    public static boolean cross(int[] stones, int k, int m) {
        int cnt = 0;
        for(int i=0;i<stones.length;i++) {
            if(stones[i] - m < 0) {
                cnt++;
            } else {
                cnt = 0;
            }
            if(cnt == k) {
                return false;
            }
        }
        return true;
    }
}