|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
class Solution {
public static boolean sectionCheck(int[] stones, int k, int mid) {
int cnt = 0;
for (int i = 0; i < stones.length; i++) {
if (stones[i] - mid < 0)
cnt++;
else
cnt = 0;
// 0미만이 k개 연속으로 나올 경우
if (cnt == k)
return false;
}
return true;
}
public int solution(int[] stones, int k) {
int answer = 0;
int mid;
int left = 1;
int right = 200000000;
while (left <= right) {
mid = (left + right) / 2;
// mid만큼의 수가 건널 수 있을 경우
if (sectionCheck(stones, k, mid)) {
left = mid + 1;
answer = Math.max(answer, mid);
} else { // 건널 수 없을 경우
right = mid - 1;
}
}
return answer;
}
}
|
cs |
건널 때 마다 0을 제외한 모든 돌들의 값들이 감소하는 것을 이용하였다.
mid명이 건넌다고 할 때 0에 상관하지 않고 mid 만큼 감소시킨다.
0미만인 돌이 k개 연속으로 나올 경우 mid명은 건너지 못한다고 판단하고 이진 탐색으로 범위를 조절한다.
건널 수 있을 경우의 mid 최댓값을 저장한다.
참고 사이트 : https://tech.kakao.com/2020/04/01/2019-internship-test/