(프로그래머스 c++ KAKAO)징검다리 건너기

이분탐색을 통해 문제 해결.

처음에는 완전탐색으로 시도했지만 효율성 테스트를 통과하지 못하므로,

이분탐색으로 문제를 풀었다.

 

front = 1, back = stones 배열에서의 max 값으로 초기화한다.

front <= back일 때까지 이분탐색 진행.

bs()함수를 정의하여 징검다리의 숫자에서 mid 값을 빼도록 한다.

mid = (front + back) / 2.

 

bs함수는 stones를 순회하면서 mid 값을 빼주면서 결과가 0 이하가 되면 count++을 해준다.

count는 징검다리의 숫자가 연속적으로 k만큼 있는지 확인하는 변수이다.

만약 stones[i] - mid 가 0이 아니라면 count = 0으로 초기화해주어, 다시 연속적인 징검다리의 개수를 세도록 한다.

순회하는 도중 count >= k가 된다면 true를 리턴하여 back = mid - 1을 해주도록 한다.

false가 반환되면 front = mid + 1.

 

결국 front가 징검다리를 건널 수 있는 친구의 수가 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

int solution(vector<int> stones, int k) {
    int answer = 0;
    int front = 1, back = *max_element(stones.begin(), stones.end());
    
    while(front <= back)
    {
        int mid = (front + back) / 2;
        
        if(bs(stones, mid, k))
            back = mid - 1;
        else
            front = mid + 1;
    }
    return front;
}