[C++]프로그래머스 징검다리 건너기(이진탐색)

코딩테스트 연습 - 징검다리 건너기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

이제 레벨3도 어거지로라도 풀어보기로 결심을 했기 때문에...

---

#include <string>
#include <vector>
using namespace std;
bool check(int n, const vector<int>& stones, int k) {
    int cur = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - n <= 0)
            cur++;
        else
            cur = 0;
        if (cur >= k)
            return false;
    }
    return true;
}
int solution(vector<int> stones, int k) {
    long long left = 1;
    long long right = 200000000;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid, stones, k))
            left = mid + 1;//최대를 구하고 싶으면 left를 옮겨라
        else
            right = mid - 1;//최소를 구하고 싶으면 right를 옮겨라
    }
    return left;//그럼 left가 정답일 것이다.
}

어제도 다뤄봤던 이진탐색(이분탐색)을 여기서도 써먹을 수 있다.

일단은 ...... 우리가 구해야하는 값은 최대 몇명이나 징검다리를 건널 수 있는가인데, 

일단 가장 단순하게 생각해봤을 때, 경우를 1부터 stone.size()만큼 차례대로 다~~~~~~~~참조하면서 거기다가 각 경우마다 for문을 돌리면서 그만큼의 사람이 건널 수 있는가를 판단하면? 늦었다.

시간복잡도 O(N^2)로, 아주 효율성이 똥이 된다.

 

그렇기 때문에~~~~~

이분탐색 쓰면 매우 조아요...

일단은 left, right를 구하는 기준은 우리가 구해야하는 최대 건널 수 있는 사람 수입니다.

stones에 올수있는 요소들의 크기가 2000000000까지 가능하기 때문에 right는 그것입니다.

이분탐색은 기본적으로

while(left <= right)
{
	int mid = (left + right) / 2;
    if()
    {
    	right = mid - 1;
    }
    else
    {
    	left = mid + 1;
    }
}

return left;

이런 형태를 띄고 있음.

결국 left , 이자....... ... mid + 1이 정답이 되는.... 그런것,,,,

이 때, if문은

최대값을 구하고 싶을 때는 if()문이 true가 됐을 때 left를 우측으로,

최소값을 구하고 싶을때는 right를 좌측으로 이동함.

이유는?

0 ~200000000

이렇게 봤을 때 우측으로 갈수록 숫자가 증가하기 때문입니다.!

 

이것만 안다면 이제 

if문에 들어갈 check함수는

이때는 for문을 써줘야 합니다.

이떄 체킹방법은,, 맨처음 주어지는 징검다리 배열에서 mid,즉 몇명 건널것인지를 빼면은 그 값이 0과 같거나 0보다 작으면 더이상 건널수없다는 것이니까 그 때마다 cnt를 증가시켜주고, 이것이 k보다 크면 건널수 없다는 것이니 false를 해주면 되겠죠.

---

이제 이분탐색.... 할수있따!