[프로그래머스 2019 카카오 개발자 겨울 인턴십] 징검다리 건너기 (파라매트릭 서치) [C++]

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

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

 

n이 20만이고 각 배열의 최댓값(m)은 2억이다.

따라서 매번 모든 배열에 -1을 빼주면서 k개 이내의 돌다리를 건너는 게 가능한지 확인하는 방법은 시간 초과가 날 것이다.

 

따라서 파라매트릭 서치를 사용했다. 이분 탐색으로 몇 번째에 건너지 못하는지를 찾는 것이다.

그렇게 되면 건너는 게 가능한지 확인하는 O(n) * 적당한 값을 이분 탐색하는 logm이므로 O(nlogm)에 해결이 가능하다.

 

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

using namespace std;

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

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