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

 이 문제는 프로그래머스 level 3 문제이다. 처음에는 완전 탐색을 이용해서 풀어보려고 했지만, 당연히 시간 초과가 났다. 징검다리의 횟수가 최대 2억번이기 때문이다.

 그래서 그 다음으로는 스택을 사용하는 것처럼 i번째에서 이전 돌들과 비교해서 같거나 큰 징검다리가 나올때까지의 횟수를 세고, 이 값이 k보다 크면 그 높이를 정답으로 내는 방식으로 풀었다. 그러나 이 방식으로는 징검다리가 내림차순으로 되어있는 경우 제대로 된 값이 나올 수 없다. 

 

 구글링을 해서 풀이를 보니 이분 탐색으로 문제를 풀 수 있었다. 입력이 큰 것부터 이분 탐색을 생각했어야 했는데 아쉬웠다. 이분 탐색을 생각만 한다면 굉장히 쉽게 풀리는 문제였다.

 

 

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

using namespace std;

bool possible(vector<int>& stones, int mid, int k) {
    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 = -1;
    
    for (int s : stones) {
        right = max(right, s);
    }
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (!possible(stones, mid, k)) {
            right = mid - 1;
        }
        else {
            answer = mid;
            left = mid + 1;
        }
    }
    
    return answer;
}