(C++) - 프로그래머스(2019 카카오 개발자 겨울 인턴십) : 징검다리 건너기

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

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

이분탐색으로 푼 문제입니다.

 

풀이방법

 최대로 건널 수 있는 인원을 찾아야합니다.

 1. 인원을 mid라고 생각했을 때 최대한으로 건넌 후의 각 돌들의 높이는 밟을 때마다 1씩줄어들기 때문에 결과적으로 돌높이 - 인원 수가 됩니다. 이 (돌높이 - 인원 수) 값이 0이하라면 건너뛰어야 하는 돌이 됩니다.

 

 2. 모든 stones에 대해 연속되는 0이하의 구간들 중 최장구간의 길이를 cnt변수에 저장합니다. 

 

 3. cnt >= k라면 너무 많은 인원이 건넌 것이므로 right = mid - 1, 반대의 경우 적은 인원이 건넜으므로 건널인원을 증가시켜주기위해 left = mid + 1로 갱신해줍니다. 

 

 4. 마지막으로 찾은 left값(인원의 최댓값)을 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> stones, int k) {
    int left = 1, right = *max_element(stones.begin(),stones.end());
    while(left <= right){
        int mid = (left + right) / 2;
        int cnt = 0;
        int maxCnt = 0;
        for(int i = 0; i < stones.size(); i++){
            if(stones[i] - mid <= 0) cnt++;
            else maxCnt = max(maxCnt, cnt),cnt = 0;
        }
        cnt = max(maxCnt,cnt);
        if(cnt >= k) right = mid - 1;
        else left = mid + 1;
        //cout << "l mid r cnt : " << left << ' ' << mid << ' ' << right << ' ' << cnt << '\n';
    }
    return left;
}