[프로그래머스] 징검다리 건너기 C++

문제 링크

내 문제 풀이 빌드업

1. n<=2십만이므로 O(N),O(logN)인 알고리즘으로 풀어야함

2. 단순 순회는 디딤돌 최대값이 2억이라 시간초과

3. 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;
}