사용한 것
- 최대 건널 수 있는 친구들의 수를 구하기 위한 upper bound
풀이 방법
l
은 1부터, r
은 200,000,001부터 upper bound를 구해준다.
- 징검다리 돌 하나 값의 최대가 200,000,000이므로 최대 200,000,000의 친구들이 건널 수 있기 때문에
r
을 200,000,001로 잡아줌
- '
num
만큼의 친구들이 건널 수 있는가?'는 'num - 1
만큼의 친구들이 건넌 뒤 마지막 친구가 건널 수 있는가?'와 같다.
stones
를 돌면서 num - 1
만큼 뺀 값이 0이거나 음수이면 ct
를 증가 시킨다. (만약 양수면 ct
를 0으로 초기화)
ct
가 k
와 같아지면 건널 수 없다는 것이므로 false를 반환한다.
코드
class Solution {
int[] stones;
int k;
public int solution(int[] stones, int k) {
this.stones = stones;
this.k = k;
int l = 1;
int r = 200_000_001;
while (l < r) {
int m = (l + r) / 2;
if (isPossible(m)) {
l = m + 1;
} else {
r = m;
}
}
return r - 1;
}
boolean isPossible(int num) {
int ct = 0;
for (int i = 0; i < stones.length; i++) {
if (stones[i] - (num - 1) > 0) {
ct = 0;
} else {
ct++;
}
if (ct == k) {
return false;
}
}
return true;
}
}