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

#include <string>
#include <vector>

using namespace std;

bool FindAnswer(int n, int k, const vector<int> &stones)
{
    int count = 0;
    
    for(int i = 0; i < stones.size(); i++)
    {
        if(stones[i] - n <= 0)
        {
            count++;
        }
        else
        {
            count = 0;
        }
        
        if(count >= k)
        {
            return true;
        }
    }
    
    return false;
}

int solution(vector<int> stones, int k) 
{    
    int start = 0;
    int end = 0;
    int mid;
    
    //find end
    for(int i = 0; i < stones.size(); i++)
    {
        end = max(end, stones[i]);
    }
    
    while(start <= end)
    {
        mid = ( start + end ) / 2;
        if(FindAnswer(mid, k, stones))
        {
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }
    
    
    return start;
}

 

풀이

1. 예상되는 n을 디딤돌마다 뺏을 때, 0이 연속되는 디딤돌이 k이상일 경우를 찾아야한다.

2. 이분탐색을 이용하여 값의 범위를 좁혀가며 답을 찾아간다.

 

 

느낀점

- 이분탐색에 대해서 더 풀어봐야겠다. 함수에 있는 식까진 나왔는데 이분탐색이 안 떠올라서 효율성테스트를 떨어졌었다.

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/64062