2019 카카오 개발자 겨울 인턴십 징검다리 건너기 ( C++ )

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

프로그래머스

 

아래의 카카오 테크 블로그에서도 해설을 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

 

위의 해설을 참고해서 이분 탐색으로 효율성을 해결했다.

m번째 친구가 다리를 건널 수 있는지 확인할 때, m-1번째 친구까지는 건넜다고 가정한다.

 

그러면 각 stone에서 m-1을 빼준 후에(m-1번째까지 건넜으므로) 연속으로 0 이하인 부분이 k개가 나오면 m번째 친구는 다리를 건널 수 없으므로 m명보다 더 적은 수로 건널 수 있는지 다시 검사한다.

 

0하인 부분이 연속으로 k개만큼 나오지 않아서 다리를 건널 수 있다면 m명보다 더 많은 친구들이 건널 수 있는지 검사한다.

 

이 m번째를 mid값으로 놓고 이분 탐색을 진행하면 된다.

이분 탐색의 초기 최댓값은 stones 배열 각 원소들의 최댓값인 200,000,000 으로 놓는다.

#include <string>
#include <vector>
#define MAX 200000000
using namespace std;
 
int maxval;
 
bool check(vector<int> stones, int k, int m) {
    //m-1번째까지는 건넜다고 가정
    int size = stones.size();
    int cnt = 0;
    for (int i = 0; i < size; i++) {
        if ((stones[i] - (m - 1)) <= 0) {
            cnt++;
            if (cnt == k) return false; //0이하가 연속으로 k면 건널수 없다.
        }
        else {
            //연속되지 않는다면 0으로 초기화
            cnt = 0;
        }
    }
    return true;
}
 
 
void binarySearch(vector<int> stones, int k, int left, int right) {
    if (left > right) return;
 
    int mid = (left + right) / 2;
    bool res = check(stones, k, mid);
 
    if (res) {
        //mid번째 친구가 건널 수 있다면 최댓값과 비교
        if (maxval < mid) maxval = mid;
 
        //mid보다 더 큰 값이 가능한지 이분 탐색
        binarySearch(stones, k, mid + 1, right);
    }
    else {
        //mid번째 친구가 건널 수 없다면 mid보다 더 작은 값 범위 탐색
        binarySearch(stones, k, left, mid - 1);
    }
}
 
 
int solution(vector<int> stones, int k) {
    int answer = 0;
 
    maxval = 0;
    binarySearch(stones, k, 1, MAX);
    answer = maxval;
 
    return answer;
}