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

이 문제의 경우 효율성 점수가 있는데 이 말인 즉슨 이분탐색을 떠올려야 한다는 뜻이다. 하지만 나는 떠올리지 못했다...(눈물) 여튼, 쉽게 풀려고하면 '돌다리 건널 수 있는지 판단하기 -> 돌다리 건너기(숫자줄이기)'로 풀 수 있지만 시간이 너무 오래걸린다. 그러므로 시간을 줄이기 위해 돌맹이가 가질 수 있는 숫자가 최대로 건널 수 있는 사람의 수라는 것을 생각하고 이분탐색으로 풀수 있다. 

 

1) 조건을 정한다.

2) 이분탐색한다.

 

1) 조건: "임의의 숫자를 뺐을 때 0보다 작은 돌맹이가 연속해서 K개 있는가?"

2) 이거 기준으로 건널 수 있는 사람의 수를 이분탐색을 진행하면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool binarySearch(int& n, vector<int>& stones, int& k){ //못건넌다!!!
    int cnt=0;
    for(int i=0;i<stones.size();i++){
        if(stones[i]-n<=0) cnt++;
        else cnt=0;
        if(cnt>=k)return true;
    }
    return false;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int Start = 1; int End = *max_element(stones.begin(),stones.end());
    while(Start <= End){
        int mid = (Start + End) /2;
        if(binarySearch(mid, stones, k)) End = mid-1; //못건너면 사람 줄여서 줄인 사람은 건널 수 있는지 알아본다.
        else Start = mid+1; //건너면 사람 늘려서 더 건널 수 있는지 알아본다.
    }
    return Start;
}

 

(+이렇게 풀면 답은 맞지만 시간초과 오류가 나게 된다.)

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0; //건넌 사람 수
    int cnt_zero = 0; // 0을 세자
    while(1){
        //돌다리 건널 수 있는지 판단하기
        for(int i=0;i<stones.size();i++){
            if(cnt_zero==k)break;
            if(stones[i] <= 0) {
                cnt_zero++;
            }
            else cnt_zero=0;
        }
        if(cnt_zero==k)break;
        //돌다리 건너기
        answer++;
     
        //돌다리 줄이기
        for(int i=0;i<stones.size();i++) stones[i] -=1;
        cnt_zero=0;
   
    }
    
    return answer;
}