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

프로그래머스

 

🇱🇻3️⃣, 징검다리 건너기[64062]

 

🧀 프로세스 

 

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

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
"니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

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

[제한사항]

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

 

🔽 문제풀이

이번 문제는 배열의 크기가  200,000개 이하라는 조건이 있다. 그렇기 때문에 단순 반복이나 재귀를 통한 확인 등과 같은 단순한 조회로는 시간 초과가 발생할 것이라고 생각했다. 사람이 지나간 곳은 무조건 1이 차감된다. 바위 N개를 제거한 뒤, 각 지점 사이의 거리가 k 이상이면 지나갈 수 없다. 그렇기에 제거할 바위의 개수를 이분 탐색을 통해 결정해가며 값을 도출하는 방식의 풀이를 고안했다.

 

public int solution(int[] stones, int k) {
    int answer = 0;
    int L = 1;
    int R = 200000000;

    while(L<=R) {
        int mid = (L + R) / 2;

        if(canCross(stones, k, mid)) {
            answer = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }

    return answer;
}

 

기존의 이분 탐색과 마찬가지로 L, R 를 조절해가며 범위를 좁혀간다.

 

static boolean canCross(int[] stones, int k, int mid) {
    int skip = 0;

    for(int stone : stones) {
        if(stone - mid < 0) {
            skip++;
        } else {
            skip = 0;
        }

        // 연속으로 건널 수 없는 다리가 k 개만큼 나온 경우 건널 수 없다고 판별
        if(skip == k)
            return false;
    }

    return true;
}

 

stone 에 mid 값을 뺐을 때 0보다 작다는 것은 그 구간부터 뛰어서 넘어야 하는 구간의 시작점이 된다. 그렇기에 skip 의 개수가 k 개를 도달하는 순간 mid 라는 인원은 다리를 건널 수 없다는 것을 의미한다. 이것으로 mid 에 대한 이분 탐색을 반복해 가며 값을 도출해 나간다.

 

✅ 전체코드 

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

        while(L<=R) {
            int mid = (L + R) / 2;

            if(canCross(stones, k, mid)) {
                answer = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }

        return answer;
    }
    
    static boolean canCross(int[] stones, int k, int mid) {
        int skip = 0;

        for(int stone : stones) {
            if(stone - mid < 0) {
                skip++;
            } else {
                skip = 0;
            }

            // 연속으로 건널 수 없는 다리가 k 개만큼 나온 경우 건널 수 없다고 판별
            if(skip == k)
                return false;
        }

        return true;
    }
}