https://school.programmers.co.kr/learn/courses/30/lessons/64062
해당 문제를 보고 이분탐색이라고 생각하지 못했고
"mid 번째 친구가 징검다리를 건널 수 있는지" 라는 문장을 힌트로 듣고 이분탐색이구나 라는 걸 알았다.
n이 200,000 정도로 클 경우 정답에 해당하는 변수가 이분탐색이 가능한지 확인해봐야겠다.
이분탐색 로직을 깔끔하게 익히지 못했었다.
결국 범위를 찾는건 이분탐색을 계속 진행하다가 최적해를 리턴하는 것이기 때문에
ans를 Max값인지 확인하고 저장해야 했으며
n명의 친구가 모두 건널 수 있는지를 true false로 리턴해야한다는 생각으로 로직을 작성했으면 더 편하게 코드를 작성할 수 있었겠다.
public static int solution(int[] stones, int k) {
long s =1;
long e = 200000000;
long ans = 0;
while (s <= e){
long mid = (s+e)/2;
// mid 에 대한 계산 -> term
int zeroCnt = 0; // 0 개수
int maxCnt = 0;
for (int num : stones){
if (num < mid){ // mid명이 못지나가는 zeroCnt가
zeroCnt++;
}
else{
zeroCnt=0;
}
maxCnt = Math.max(maxCnt,zeroCnt);
}
// n명이 건널 수 있는 다리가 k개 이상이면
// maxCnt 가 0 .. k-1까지 가능, k부터 불가능
// 가능하면
if (maxCnt < k){
ans = Math.max(ans,mid); // 최신화
// 인원 늘리기
s = mid+1;
}
else{
// maxCnt == k 또는 그 이상이라는 말은 건널 수 없음
// 인원 줄이기
e = mid-1;
}
}
return (int) ans;
}