[이분 탐색] 징검다리 건너기 - 2019 카카오 개발자 겨울 인턴십

코딩테스트 문제가 이분 탐색 문제인지를 확인할 수 있는 꼼수가 있다. 그것은 주어진 값의 범위를 확인하는 것이다.

이 문제는 주어진 범위를 아무리 잘 조합해봐도 복잡도가 터무니없는 수(억 단위)가 나온다. 보통 코딩테스트에서 효율성을 따질 때 최대 복잡도가 억 단위 이상이 나오면 거의 실패한다.

이분 탐색은 값을 미리 가정하고 푸는 알고리즘이다. 처음으로 가정하고 싶은 값은 어떠한 값을 골라도 상관이 없지만 보통 중간값을 선택한다.

 

 

해결 방법

중간값을 m으로 지정했다면 m명이 모두 징검다리를 건널 수 있는지를 체크해야 한다. m명이 모두 건널 수 없다면 m명 이상인 경우는 전부 건널 수 없다는 뜻이므로 범위의 최댓값을 m-1명으로 지정하고, m명이 모두 건널 수 있다면 범위는 m명~2억명 사이에 있다는 뜻이므로 범위의 최솟값을 m+1명으로 지정한다.

그리고 m명이 모두 징검다리를 건널 수 있다면 이 경우의 m은 정답의 후보가 되고, 이 경우의 모든 m의 최댓값이 이 문제의 정답이 된다.

 

 

소스 코드

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

int solution(vector<int> stones, int k) {
    int answer = 0;
    int s,m,e; // 시작, 중간, 끝 지점
    s=0; e=200000000;
    int cnt; // 밟지 못하는 디딤돌의 연속 카운트
    bool result=true; // m명이 모두 징검다리를 건널 수 있는가?
    
    while(s<=e){
        m=(s+e)/2;
        vector<int> v; // stones 배열 복사
        v.resize((int)(stones.size()));
        copy(stones.begin(),stones.end(), v.begin());
        
        // m-1명이 모두 징검다리를 건넜을 경우의 상태
        for(int i=0;i<v.size();i++){
            v[i]-=(m-1);
            if(v[i]<0) v[i]=0;
        }
        
        // m번째 사람이 징검다리를 건널 수 있는지 체크
        cnt=0;
        result=true;
        for(int i=0;i<v.size();i++){
            if(!v[i]) cnt++;
            else cnt=0;
            if(cnt==k) {
                result=false;
                break;
            }
        }
        
        if(!result) e=m-1; // 건널 수 없다면 끝점을 움직여 범위를 반으로 줄인다.
        else {
            answer=max(answer, m); // 건널 수 있다면 m은 정답 후보
            s=m+1; // 시작점을 움직여 범위를 반으로 줄인다.
        }
    }
    return answer;
}

 

 

정확성, 효율성 모두 만점