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

문제 바로가기

 

[문제 설명]

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

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

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

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

[제한사항]

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

[입출력 예]

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

입출력 예 #1

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

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

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

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

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

 

[문제 풀이]

(첫번째 시도)

정확성 1번, 효율성 13/14 실패

class Solution {     public int solution(int[] stones, int k) {         int min = Integer.MAX_VALUE; //정답, 징검다리를 건널 수 있는 최대의 사람         int max = stones[0]; // start지점부터 start+k 지점까지 건널 수 있는 최대의 사람 수         int start = 0; // 현재 징검다리의 인덱스         while (start + k < stones.length) {             if (max == stones[start]) {                 max = 0;                 for (int i = start + 1; i <= start + k; i++) {                     if (stones[i] > max) max = stones[i];                 }                 if (min>max) min = max;             }             start++;         }         return min;     } }

첫번째 시도는

징검다리를 하나씩 건너며 현재 징검다리(start)가 max값과 같다면,

max값을 (start+1) 에서 (start+k)까지 조회하여 max값을 다시 갱신하는 방법이다.

그 max값 중에서 가장 작은 값을 정답으로서 반환하는 알고리즘이다.

 

[문제점] 이 알고리즘은 (stones.length - k) 지점 까지만 조회하고 있다. 이는 (stones-k)~(stones.length)지점을 조회하고 있지 않는데 즉, 맨 마지막 지점을 조회하고 있지 않다(정확성 1번, 효율성 14번). 또한 [99999, 99998, 99997, 99996, 99995, ...... ,1] stones의 구성이 이렇게 되어있다면 시간초과(효율성13번)가 걸리게 된다.

 

(두번째 시도, 정답)

class Solution {     public int solution(int[] stones, int k) {         int answer = 0;         int min = 1; // 건널 수 있는 최소의 사람         int max = 200000000; //건널 수 있는 최대의 사람         while (min <= max) {             int mid = (min + max) / 2;             if (check(stones, k, mid)) { //만약 mid가 건널 수 있다면                 min = mid + 1;                 answer = Math.max(answer, mid);             } else max = mid - 1; //mid가 건널 수 없다면         }         return answer;     }     public boolean check(int[] stones, int k, int number) {         int stride = 0; //연속으로 몇 개의 징검다리를 건너는 지 변수         for (int stone : stones) {             if (stone - number < 0) { // number명이 징검다리를 건널 수 없다                 stride++;             } else stride = 0; //number명이 건널 수 있으므로 0으로 초기화             if (stride == k) return false; //건널 수 없는 다리가 연속으로 k개가 된다면 이 다리는 number명으로 건널 수 없다.         }         return true;     } }

첫번째 시도 이후 이분탐색을 사용해보라는 조언이 있어서 시도해보았다.

이분탐색에서 우리가 조회할 것은 최대 몇 명의 사람이 건널 수 있을지를 조회하는 것이다.

예를 들자면, 5천명의 사람이 건널 수 있는지 조회를 해보고 안된다면 2500명으로 줄여서 조회하고 그래도 안된다면 1250명으로 조회하는 것이다. 다른 예로 5천명의 사람이 건널 수 있다면 7500명으로 늘려보는 방식이다.

 

5천명의 사람이 건널 수 있을 지 체크하는 것은 매우 간단하다. stones[0] 부터 끝까지 5천명의 사람이 연속적으로 건널 수 없는 경우 중에  k개보다 크거나 같지 않다면 건널 수 있다.

4999

4998

5000

5001

4999

4989

5000

4999

4893

5000

여기서 5천 명을 빼본다면

-1

-2

0

1

-1

-11

0

-1

-107

0

위와 같이 되는데 입출력 예 #1을 본다면 k = 3인 check(stones, 3, 5000)은 true값이 된다.

 

true값이 된다면 5천명에서 더 늘려서 check 메소드를 실행하고 적다면 5천명에서 줄여서 check메소드를 실행한다.