[프로그래머스 Level.3] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 > 징검다리 건너기

 

 

 

문제 설명

 

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

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

 

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 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

 

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

 

 

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

 

 

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

 

 

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

 

 

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

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        // target => 징검다리를 건널 수 있는 친구의 수
        int start = 1; // 최소
        int end = 200000000; // 최대 (stones 원소의 최댓값)
        
        while(start <= end) {
            int mid = (start + end) / 2;
            int skip = 0;
            boolean canCross = true;
            
            // skip이 연속으로 증가하여 k 이상이 되면 건널 수 없음
            for(int stone : stones) {
                if(stone - mid < 0)
                    skip++;
                else 
                    skip = 0;
                
                if(skip >= k) {
                    canCross = false;
                    break;
                }
            }
            
            if(canCross) { // 건널 수 있음 -> 친구의 수를 늘려 더 최선의 경우를 찾음
                answer = mid;
                start = mid + 1;
            } else { // 건널 수 없음 -> 친구의 수를 줄여 탐색
                end = mid - 1;
            }
            
        }
            
        return answer;
    }
}

 

풀이

1. 최대 건널 수 있는 니니즈 친구들의 수가 상당히 크므로 이분 탐색(Binary Search)을 이용하여 탐색 범위를 반 씩 줄여가며 푸는 문제이다.
2. 건널 수 있는 친구들의 수를 구하는 문제이므로 target을 건널 수 있는 니니즈 친구들의 수로 하고 최소 건널 수 있는 경우의 수인 1을 start로 하고 최대로 건널 수 있는 경우의 수인 200000000(stones 배열 원소의 최댓값)를 end로 한다.
3. 이제 start가 end 이상이 되면 종료하는 while문을 생성한다.
4. start와 end를 더해 2로 나눈 중간값을 mid에 저장한다.
5. 이제 mid(니니즈 친구들의 수)가 모두 징검다리를 건널 수 있는지 체크해야 한다.
6. 연속으로 점프해야 하는 디딤돌의 수를 나타내는 int형 변수 skip과 건널 수 있는지를 나타내는 boolean형 변수 canCross를 true로 생성한다.
7. 주어진 배열 stones를 돌면서 stone - mid가 0보다 작으면 skip해야 하는 니니즈 친구들이 생기므로 skip을 1 증가시키고 0보다 같거나 크다면 점프해야 하는 디딤돌이 아니므로 skip을 0으로 다시 초기화한다.
   (stone - mid < 0으로 하는 이유는 stone과 mid의 수가 같다면 mid 수 만큼은 밟고 건널 수 있지만 stone이 mid 보다 작아지면 밟을 수 없고 점프해야 하기 하기 때문이다. 예를 들어 stone = 3 이고 mid = 3 이라면 3 - 3으로 3명까지 건널 수 있는 것이지 점프하는 것(skip)이 아니다.)
8. skip이 연속으로 증가하여 k 이상이 되면 니니즈 친구들이 mid의 수만큼 건널 수 없는 것이기 때문에 canCross를 false로 하고 for문을 나오고 아니라면 계속 for문을 진행한다. (k가 3이라면 2개까지 점프하여 3번째 디딤돌을 밟아야 하므로 skip이 k와 같다면 건널 수 없는 것이다)
9. 이렇게 for문을 돌고 나와서 canCross가 true라면 mid의 수만큼 모두 건널 수 있는 것이기 때문에 answer를 mid로 하고 start를 mid + 1로 하여 니니즈 친구들의 수를 증가시켜 더 건널 수 있는지 확인하기 위해 다시 반복하고 canCross가 false라면 mid의 수만큼 모두 건널 수 있는 것이 아니기 때문에 end를 mid - 1로 하여 니니즈 친구들의 수를 감소시켜 다시 반복한다.
10. 이렇게 탐색범위를 줄여가며 탐색하다가 start가 end보다 커지게 되면 반복문을 종료하고 건널 수 있는 최대의 수를 저장한 answer를 반환한다.