[프로그래머스] 징검다리 건너기 C++ (Lv.3)

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/64062?language=cpp 

프로그래머스

 

이번 문제는 이분 탐색 또는 슬라이딩 윈도우 문제였습니다.

글쓴이는 이분 탐색으로 풀이했습니다. 💭

 

 

 

 

📝 문제 풀이

1. stones 배열 각 원소들의 값은 1 이상이므로 s는 1, e는 stones 배열의 최댓값으로 초기화

2. s <= e 일 때 동안 while 문을 돌면서 현재 mid 값만큼의 니니즈 친구들이 징검다리를 건널 수 있는지 체크

     ➡️ mid 값보다 작거나 같은 돌이 연속으로 k개 이상 있으면 mid 값만큼의 니니즈 친구들이 징검다리를 건널 수 없으므로 false 반환 ⭐️

3. false이면 니니즈 친구들의 수를 줄여야 하므로 e = mid - 1

4. true이면 니니즈 친구들의 수를 늘려야 하므로 s = mid + 1

5. s가 e보다 커지면 s 반환

 

 

 

 

👩🏻‍💻 C++ 코드

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

using namespace std;

bool isPossible(int mid, int k, vector<int> &stones) {
    int cnt = 0;
    
    for (int i=0; i<stones.size(); i++) {
        if (stones[i] <= mid) cnt++;
        else cnt = 0;
        
        // mid보다 작거나 같은 숫자가 적힌 돌이 연속으로 k개 이상있으면 건널 수 없음
        if (cnt >= k) return false;
    }
    
    return true;
}

int solution(vector<int> stones, int k) {
    int s = 1;
    int e = *max_element(stones.begin(), stones.end());
    int mid;
    
    while (s <= e) {
        mid = (s + e) / 2;
        
        if (isPossible(mid, k, stones)) s = mid + 1;
        else e = mid - 1;
    }
    
    return s;
}

 

프로그래머스 - 결과 화면