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

문제 링크

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

문제 설명

카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디-

• 딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
  디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여
  러 칸을 건너 뛸 수 있습니다.

• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

알고리즘: 이분 탐색

이 문제는 규칙을 지키면서 최대 몇 명까지 징검다리를 건널 수 있는지 구하는 문제다.

징검다리를 한 명이 건넜다고 해보자, 수가 남아있는 모든 돌에 -1을 해야 한다. 즉 남아있는 모든 돌은 사람이 지나갈 때마다 한 번씩 밟을 수밖에 없다.

그렇다면 징검다리를 건너는 사람이 증가할수록 돌에 적힌 숫자가 더 감소한다는 얘기이고
반대로 징검다리를 건너는 사람이 감소할수록 돌에 적힌 숫자가 덜 감소하게 된다.

위 문장을 보고, 이분 탐색을 어느 정도 풀어본 사람이라면 단번에 이분 탐색 알고리즘을 떠올려야 한다.

결론은 이분 탐색 문제다.

min 값은 최소 한 명은 징검다리를 지나갈 수 있기 때문에 1이다.
max 값은 최대 200,000,000명이다. -> (배열 각 스톤의 최댓값이 200,000,000이기 때문에 그 이상은 지나갈 수 없음)

이제 mid가 true, false인지만 판단해주면 된다.
내가 판단해준 방법은 이렇다. mid가 3이라고 할 때
2명이 건넜을 때 스톤 값을 살펴본다. -> 각 스톤 값에 -2를 해주면 됨.
그리고 0보다 작거나 같은 연속적인 돌의 개수를 세준다. -> 순차 탐색
만약에 그 개수의 + 1(+1은 현재 돌)이 k보다 클 경우 남은 한 명은 건널 수 없기 때문에 false를 반환 해주면 된다.
여기서 -3이 아니고 -2를 해주는 이유는 -3을 해줬을 때 3명이 다 건너갈 수 있는지 판단하기가 애매하다.
ex)
1. [2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k = 3
2. [2, 4, 5, 2, 2, 1, 4, 2, 5, 1], k = 3
-3 했을 때 스톤 값이 같지만 1번째 경우는 3명이 지나갈 수 있고 2번째 경우는 2명만이 지나갈 수 있다.
그래서 3-1인 2명이 먼저 지나간 상태에서 나머지 한 명이 지나갈 수 있는지 순차 탐색으로 확인하면 stones.length 횟수만으로 판단할 수 있다.

시간 복잡도는 O(N * log M)로 약 5백만이다. (N은 stones 배열의 크기, M은 200,000,000)

소스 코드

import java.util.*;
class Solution {
    public int solution(int[] stones, int k) {
        return binary_search(stones, k);
    }
    
    static int binary_search(int[] stones, int k) {
        int min = 1;
        int max = 200000000;
        while(min <= max) {
            int mid  = (min + max) / 2;
            if(check(mid, stones, k)) min = mid + 1;
            else max = mid - 1;
        }
        return max;
    }
    
    static boolean check(int v, int[] stones, int k) {
        int zero = 0;
        for(int i=0; i<stones.length; i++) {
            if(stones[i] - (v-1) <= 0) zero += 1;
            else zero = 0;
            //반드시 점프해야하는 횟수 (zero + 1)가 k보다 커진다면 false;
            if(zero + 1 > k) return false;
        }
        return true;
    }
}