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

[문제]

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

[풀이]

 

반복문을 사용해 한 명씩 보내면서 구할 수 있다.

하지만 stones 배열의 길이가 200,000이므로 시간초과가 발생하여 효율성 부분에서 틀린다.

따라서 이분 탐색을 사용하여 찾아가는 방식으로 하였다.

(이분탐색 정리 : https://tnwlswkd.tistory.com/112 )

 

stones 배열에서 left는 1, 가장 큰 값으로 right를 초기화 한다.

중간 값을 구해가면서 left, right 값을 조절하여 건널 수 있는 학생수의 최댓값을 찾는다.

 

mid를 기준으로 mid 값보다 stones의 값이 작다면 mid만큼의 학생이 건너지 못하는 것이므로 cnt+=1을 해준다. 또한 이러한 경우가 연속으로 k번 이상이라면 mid 만큼의 학생이 건너지 못하므로 false를 return하여 mid 값을 조절한다.

 

이러한 방식으로 left>right일 때까지 반복하여 이분탐색을 통해 최댓값을 찾을 수 있다.

 

[코드]

 

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

using namespace std;
bool binary_search(vector<int> stones, int k, int mid)
{
    int cnt =0;
    for(int i=0;i<stones.size();i++)
    {
        if(stones[i] < mid )    cnt++;
        else    cnt=0;
        
        if(cnt >= k)    return false;
    }
    return true;
}

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