n<=2십만이므로 O(N),O(logN)인 알고리즘으로 풀어야함
단순 순회는 디딤돌 최대값이 2억이라 시간초과
logN의 대표적인 알고리즘인 이분탐색으로 풀었지만, 윈도우 슬라이딩이나 정렬 등 여러 방법도 가능할 것 같았음
금주에 보는 코테 언어 중 js가 없어서 다시금 c++을 공부했더니 까먹은 stl이 많았다 😥
이분 탐색의 기준을 건널 수 있는 사람 수가 아닌 돌의 값이라는 생각을 못함. 같은 말이지만 머릿 속에서 정리되지 않았다ㅜ
돌의 값이 k보다 작을때 스킵해야하는데 작거나 같을 때로 조건화 해서 계속 실패가 떴다.
int solution(vector<int> stones, int k) {
int answer = 0;
//디딤돌 값의 최대 최소 구하기
int start=*min_element(stones.begin(),stones.end());
int end=*max_element(stones.begin(),stones.end());
int mid;
//이분 탐색
while(start<=end){
mid=(start+end)/2;
//skip해야하는 돌의 수와 그 중 최대
int skip=0,maxSkip=0;
for(int i=0;i<stones.size();i++){
//돌이 mid보다 작으면 스킵해야함
//같을때는 건널 수 있음. 건너고 나서 0이 됨
if(stones[i]-mid<0) skip++;
else skip=0;
maxSkip=max(skip,maxSkip);
//if문을 for문 밖에 넣어도 되지만
//stones의 길이가 길 경우 굳이 다 돌지 않기 위해
if(maxSkip>=k){
end=mid-1;
break;
}
}
//스킵 횟수가 k보다 작으면 start값을 크게
if(maxSkip<k){
answer=max(answer,mid);
start=mid+1;
}
}
return answer;
}