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

문제

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

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

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

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

---

접근

문제요약

1. k보다 크게 점프 못함.

2. 한명이 지나가면 모든 돌에 있는 수가 하나씩 작아짐.

 

그러니까

어떠한 숫자로 지나갈 수 있는 경우 최대를 구하면 됩니다.(최대인 이유는 최대한 많은 사람이 지나가길 원하기 때문)

 

예제

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k=3

이 경우 1로 지나간다고 했을 때,

위의 값을 순차적으로 탐색하며,

1보다 크거나 같을 때 cnt를 0으로,

1보다 작을 때, cnt를 +1해주다가

cnt가 k와 같아지면 그건 해당 숫자로 못지나가는 경우 입니다.

 

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] , k=3 이 예제의 경우

2가 1보다 크므로 cnt = 0

4가 1보다 크므로 cnt = 0

...

항상 cnt가 0이므로 통과가능

 

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] , k=3 이 예제의 경우 (2로 했을 때)

2가 2보다 크거나 같으므로 cnt = 0

4가 2보다 크므로 cnt = 0

5가 2보다 크므로 cnt = 0

...

1이 2보다 작으므로 cnt = 1

4가 2보다 크므로 다시 cnt = 0

...

cnt 가 k값인 3이되지 않으므로 이것도 통과!

 

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1], k=3 이 예제의 경우 (4로 했을 때)

2가 4보다 작으므로 cnt = 1

4가 4보다 크거나 같으므로 cnt = 0

5가 4보다 크므로 cnt = 0

3,2,1은 4보다 작으므로 cnt=3

즉

[0,0,1,0,0,0,0,0,1,0] 이 경우 3보다 더 큰 점프를 해야하므로 불가능합니다.

이렇게 안되는 경우를 찾으면 이 후 값은 모두 안되므로(4,5,6,7 .. .모두 안됨)

되는 값들 중 최대값을 찾으면 됩니다.

 

이것을 위 방식대로 1,2,3 순서대로 찾으면 너무 오래 걸리기 때문에, 이분탐색을 이용해야 합니다.

최솟값이 1이고 최댓값이 200,000이니까 이를 이용해서 이분탐색을 이용하면 문제가 해결됩니다.

 

---

코드

import java.util.*;
class Solution {
    public boolean binarySol(int stones[], int k, int mid){
        int cnt = 0;
        for(int stone : stones){
            if(stone < mid){
                cnt++;
            }
            else{
                cnt = 0;
            }
            if(cnt == k) return false;
        }
        return true;
    }
    public int solution(int[] stones, int k) {
        int answer = (int)1e9;
        int start = 1;
        int end = 200000000;
        while(start <= end){
            int mid = (start + end)/2;
            if(binarySol(stones, k, mid)){
                answer = mid;
                start = mid +1 ;
            }
            else{
                end = mid - 1;
            }
        }
        return answer;
    }
}

---

주의

x