프로그래머스. 징검다리 건너기(c++) / 이분탐색

잘못된 테케를 넣는 바람에 괜히 시간을 날렸던 문제....^^

그냥 원래 짰던 코드가 맞았던 건데 테케를 잘못 넣어서 괜히 시간 낭비를 해버렸다....으이ㅏ아아아

 

[메인 로직]

디딤돌에 적혀있는 숫자들 중 가장 작은 수와 큰 수를 기준값으로 정하고

이분탐색을 시작했다.

mid값을 각 디딤돌에 적힌 수에서 빼고 돌다리를 건널 수 있는 지 여부를 판단했다.

 

#include <string>
#include <vector>
#include <climits>
 
using namespace std;
 
int solution(vector<int> stones, int k) {
    int answer = 0;
    
    // 이분탐색으로 제거할 수를 찾기
    int Min = INT_MAX, Max = 0;
    
    for(int i=0; i<stones.size(); i++){
        Max = max(Max, stones[i]);
        Min = min(Min, stones[i]);
    }
    
    while(Min<=Max){
        int mid = (Min+Max)/2;
        
        int cnt = 0;
        bool check = false;
        for(int i=0; i<stones.size(); i++){
            int num = stones[i]-mid;
            if(num<=0){
                cnt++;
            }else{
                cnt = 0;
            }
            if(cnt>=k){
                answer = mid;
                check = true;
                Max = mid-1;
                break;
            }
        }
                
        if(check==false){
            Min = mid+1;
        }   
    }
    
    return answer;
}