문제

2019 카카오 개발자 겨울 인턴십 징검다리 건너기

🪨 징검다리 건너기 (카카오 문제 요약)

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍 중 개울을 건너기 위해 징검다리를 건너야 한다.
각 디딤돌에는 숫자가 쓰여 있으며, 밟을 때마다 숫자가 1씩 감소한다.

🔍 규칙 정리

• 디딤돌은 일렬로 놓여 있으며, 각 디딤돌은 밟을 때마다 숫자가 1 감소한다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없다.
• 밟을 수 없는 돌이 나오면, 그 다음 돌로 여러 칸 건너뛰어 이동할 수 있다.
• 단, 건너뛸 때 여러 칸 중 가장 가까운 돌만 선택할 수 있다.
• 친구들은 한 명씩 순차적으로 징검다리를 건넌다.
• 친구가 모두 건넌 후에 다음 친구가 출발한다.
• 개울의 오른쪽 건너편에 도착해야 "건넌 것"으로 인정한다.

🧮 문제 요구사항

• 주어진 배열 stones는 각 디딤돌의 초기 숫자(내구도)를 의미한다.
• k는 한 번에 건너뛸 수 있는 최대 칸 수이다.
• 이 조건에서, 최대 몇 명의 친구가 무사히 징검다리를 건널 수 있는지 구하는 문제.

📌 제한사항

• 니니즈 친구 수는 무제한이라고 가정한다.
• stones 배열 길이: 1 ~ 200,000
• 각 디딤돌 값: 1 ~ 200,000,000
• k: 1 ~ stones.length

🧪 예시

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

3명까지는 건널 수 있지만, 4번째는 연속으로 밟을 수 없는 디딤돌 구간이 생겨 건너지 못한다.

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.

네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

문제 분석

이 문제를 처음 보았을 때는 배열을 돌면서 조건을 확인하는 완전탐색이 가장 떠올랐지만, 완전탐색으로는 절대 풀 수 없는 문제이다.

왜 완전탐색이 불가능한가?

입력 크기

• 돌 개수: 최대 200,000
• 돌 내구도: 최대 200,000,000
• 친구 수는 사실상 무한대

만약 “1명, 2명… 계속 증가시키며 완전탐색”을 시도하면
억 × 억 수준의 연산이 발생하여 절대로 시간 내에 못 끝난다.

핵심 아이디어: ‘몇 명이 건널 수 있는지’를 이분탐색하기

이 문제는 “정답을 직접 찾는” 문제가 아니라
“정답을 가정하고 가능한지 체크하는” 이분탐색으로 접근해야 하는 문제다.

이분탐색이란 정렬된 배열에서 원하는 target 값을 찾는 방법이다.
이 값을 찾기 위해서는 배열의 중간 값을 mid로 두고 target이 mid 보다 큰지 작은지를 판단하여 범위를 좁혀나간다.

이분탐색은 시간복잡도가 O(logN)이기 때문에 이 문제처럼 배열의 크기가 어마무시하게 큰 경우에 효율적으로 사용될 수 있다.

이분탐색 예시 코드는 아래와 같다.

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {            
            int mid = (left + right) / 2;

            if (arr[mid] == target) {
                return mid;                 // Target 발견
            } else if (arr[mid] < target) {
                left = mid + 1;             // 오른쪽으로 범위 이동
            } else {
                right = mid - 1;            // 왼쪽으로 범위 이동
            }
        }

        return -1; // 찾지 못한 경우
    }
}

그러나, 이 문제는 정렬된 배열에서 특정 값을 찾는 문제가 아니고
조건을 만족하는 최댓값을 찾는 문제이다.
이런 경우에는 파라메트릭 서치를 사용할 수 있다.

파라메트릭 서치는 이분탐색과 비슷하지만 이분탐색과 달리 주어진 일련의 배열에서 찾는 것이 아니라 특정 범위 내에서 원하는 조건에 일치하는 값을 찾는 방법이다.

설계 스크래치

탐색 범위

• 최소 건널 수 있는 인원: 1명
• 최대 건널 수 있는 인원: max(stones)
  (가장 큰 내구도를 가진 돌이 버틸 수 있는 최대 인원)

즉,
left = 1
right = max(stones)
로 두고 탐색을 시작한다.

mid명의 친구가 건널 수 있는지 확인하기

mid명을 보냈다고 “가정”하면,
모든 돌의 내구도는 stones[i] - mid가 된다.

이때 연속해서 mid명을 버티지 못하는 돌(= 음수가 된 돌) 이
k개 이상 연속으로 등장하면 → 건너지 못함.

왜 “0 이하”가 아니라 “음수(<0)”로 체크해야 할까?

배열에서 stones[i] - mid를 계산할 때,

• “mid명이 모두 지나간 후”의 값을 계산하는 것임
• 돌의 값이 0이라는 것은 지나갈 당시에는 양수였다는 의미

즉, 0은 건널 수 있었던 상태다.
때문에 조건은 반드시 stones[i] - mid < 0 (음수) 로 체크해야 한다.

설계 코드

1. 파라메트릭 서치 과정

    public int solution(int[] stones, int k) {
        int left = 1; //최소 건널 수 있는 친구의 수 
        //최대 건널 수 있는 친구의 수 (stones의 최댓값)
        int right = Arrays.stream(stones).max().getAsInt();

		//left가 right보다 작을 때까지 반복한다.
        while (left <= right) { 
        	//중간값 설정
            int mid = (left + right) / 2;
            
            // mid명이 못 건너면 → 인원수를 줄여야 함
            if(canCross(mid, stones, k) == -1) {
                right = mid -1;
             // mid명이 건너면 → 더 많이 보낼 수 있는지 확인
            } else  {
                left = mid + 1;
                
            } 
        }
        // right는 ‘가능했던 최대 mid’가 된다.
        return right;
    }

2. mid명의 친구가 징검다리를 건널 수 있는지 검증하는 과정

    public int canCross(int mid, int[] stones, int k) {
    // 연속으로 음수가 되는 돌 개수
        int currStoneChain = 0;
        
        for (int i = 0; i < stones.length; i++) {
        // mid명의 친구가 밟고 난 후 음수 → 밟을 수 없음

            if (stones[i] - mid < 0) {
               currStoneChain += 1;
               
               //연속된 돌의 수가 k 이상이면 건널 수 없다.
                if (currStoneChain >= k) {
                    return -1;
                }
            } else { 
            //연속이 끊기면 초기화
                currStoneChain = 0;
            }
        }
        //mid명은 건널 수 있다.
        return 1;
    }

전체 흐름 요약

✔️ mid명을 보낸다고 가정하고
→ stones 배열에서 mid를 뺀 결과가 음수인지 확인하며
→ 연속된 음수 개수가 k 이상이면 실패
✔️ 이 과정을 이분탐색으로 반복
→ 가능 여부만 확인하며 범위를 좁혀감
✔️ 결국 가능한 최대 mid(right)가 정답

주의할 점

1. 파라메트릭 서치의 return 값이 right가 되는 이유

종료 직전 시점은 항상:
right = 건널 수 있었던 가장 큰 mid
left = 건널 수 없는 첫 mid
즉,
right는 “가능한 최대 인원수”이고
left는 “불가능한 최소 인원수”가 된다.
그래서 return 값은 right.

2. mid명의 친구가 건널 수 없는 조건을 검증할 때 0이하가 아니라 음수가 되는 이유

문제에서는 돌의 수가 0이 되면 건널 수 없다고 되어 있는데 코드에서는

if (stones[i] - mid <= 0) {

이 아니라

if (stones[i] - mid < 0) {

으로 한 이유는,
해당 stones[i] - mid는 mid명이 밟고 난 후의 값이기 때문이다.
밟고 난 후, 돌의 숫자가 0이 되었다는 것은 지나갈 때는 양수였다는 의미이기 때문에 지나가는 것이 가능하다는 의미이다.

3. 돌을 밟은 후 숫자를 구할 때 배열을 직접 변경해서는 안된다.

처음에는 조건을 아래와 같이 썼다.
아래와 같이 배열의 값을 직접 변경하게 되면, 다음 이분탐색 때 배열이 달라져서 올바른 값을 구하지 못한다.

프로그래머스의 예제 1번에서는 1번만 검증을 해도 답이 나오기 때문에 예제는 맞추는데 다른 테스트케이스는 모두 틀리는 불상사가생긴다.

int result = stones[i] -= mid;
if (result < 0) {

그렇기 때문에 값을 직접 변경하지 말고 아래처럼 조건문으로 쓰도록 하자

if (stones[i] - mid < 0) {