프로그래머스 - 징검다리 건너기 (Lv.3)

문제 링크

• 징검다리 건너기

문제 접근

• 효율성을 통과해야 하기 때문에 시간복잡도를 최소화 해야 한다.
• 목표는 징검다리를 건널 수 있는 최대 학생 수를 찾는 것이다. 즉, 징검다리를 어떻게 건너는지에 대한 로직이 아니라 n명이 징검다리를 건널 수 있는지 파악하고, 건널 수 없을 때 n명을 어떻게 조정할 것인지를 생각해야 한다.
• 최대로 건널 수 있는 학생 수는 주어진 stones의 최댓값이다. ( max_student )
• 최소로 건널 수 있는 학생 수는 1명이므로, 1~max_student 에 해당하는 학생 수로 이분탐색을 한다.
• 건널 수 있는지 없는지를 판단하는 방법은 stones 배열에서 mid 값을 뺐을 때 음수값으로 존재하는 연속 구간이 k 보다 작은지 크거나 같은지를 판단하면 된다.

구현(All Pass)

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

using namespace std;

bool check_cross_stones(vector<int>& stones, int mid, int k){
    int cnt = 0;
    for(int i=0; i<stones.size(); i++){
        if(stones[i]-mid < 0) cnt++;
        else cnt = 0;
        if(cnt>=k) return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int max_student = *max_element(stones.begin(), stones.end());
    int answer = 0;
    
    // 이분탐색으로 징검다리를 건널 수 있는 학생 수를 찾아간다.
    // mid 에서 건너지 못한다면, right = mid - 1 로 바꿔서 탐색
    // mid 에서 건널 수 있다면, mid 이하인 값들에서는 건널 수 있으므로 left = mid+1 로 바꿔서 탐색
    int left = 1, right = max_student;
    int mid = 0;
    while(left<=right){
        mid = (left+right)/2;
        if(check_cross_stones(stones, mid, k)){
            answer = mid;
            left = mid + 1;           
        }
        else{
            right = mid - 1;
        }
    }
    
    return answer;
}