[프로그래머스] 카카오 윈터 인턴십 2019 - 징검 다리 건너기 (Java)

https://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의 길이 이하인 자연수입니다.

---

[입출력 예]

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

---

풀이

효율성 테스트가 없었다면 각 원소들을 1씩 차감시켜 연속되는 0이 k번 이상인 경우를 체크해줘서 쉽게 풀이가 가능하다.

하지만 stones 배열의 원소는 최대 200,000,000까지 될 수 있기 때문에 이 방법을 이용하게되면 최대 200,000,000번 즉, O(N)만큼의 시간 복잡도가 걸리기 때문에 효율성 테스트를 통과할 수 없다.

 

0부터 N까지 차례로 올라가며 다리를 건널 수 있는지 파악하는 방법보다 더 빠르게 값을 찾아내기 위해 이진탐색을 사용했다. 이진 탐색의 경우 O(logN)으로 일반적인 for문에 의한 탐색보다 더 효율적으로 탐색이 가능하다.

시작값은 0, 끝값은 stones 배열의 원소중 최대값으로 둔다.

시작값과 끝값의 중간 값 mid를 구하고 mid만큼 니니즈 친구들이 지나간다고 할 때

이 때 건너는 것이 가능하다면 mid 이상의 더 많은 친구들이 건널 수 있기 때문에 start = mid + 1로 변경하고 다시 탐색을 시작한다.

반대로 불가능하다면 mid 보다 적은 수의 친구들이 건너갈 수 있는 것이기 때문에 end = mid - 1로 변경하고 다시 탐색을 시작한다.

탐색은 start가 end 보다 커질 때까지, 즉 두 지점이 만나지 않을 때까지 진행하고, 만나는 지점이 답이 된다.

 

코드

public class Solution {
    private int limit;
    private int answer;

    public int solution(int[] stones, int k) {
        limit = k;
        int max = Integer.MIN_VALUE;

        for (int stone : stones) {
            max = Math.max(max, stone);
        }

        binarySearch(stones, 0, max);

        return answer;
    }

    private void binarySearch(int[] stones, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            int[] cloneStones = setStones(stones.clone(), mid);

            if (isPossible(cloneStones)) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        answer = start;
    }

    private boolean isPossible(int[] stones) {
        int count = 0;

        for (int i = 0; i < stones.length; i++) {
            if (stones[i] == 0) {
                count++;
            } else {
                count = 0;
                continue;
            }

            if (count == limit) {
                return false;
            }
        }

        return true;
    }

    private int[] setStones(int[] stones, int value) {

        for (int i = 0; i < stones.length; i++) {
            if (stones[i] <= value) {
                stones[i] = 0;
            }
        }

        return stones;
    }
}