[프로그래머스 lv3] 징검다리 건너기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

해당 문제는 2019 카카오 개발자 겨울 인턴십 출제 문제로 공식 해설이 있습니다.

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

 

다양한 풀이가 있겠지만, 이분탐색 풀이를 선택해보자.

가능한 니니즈수에 대하여 이분탐색을 진행하면 징검다리를 건널 수 있는 최대 니니즈수를 log(m) 에 탐색할 수 있다. (m=200000000)

 

이때, 특정 니니즈 수 x에 대하여 최대 칸수 k내에서 징검다리를 모두 건널 수 있는지 확인해야 한다.

x-1명까지 건넜을 때 디딤돌 배열 상태는 stones[i]를 min(0, stones[i]-(x-1))로 변경하여 구할 수 있는데, 배열에서 연속적으로 등장하는 0의 개수가 모두 k보다 작거나 같으면 모두 징검다리를 건널 수 있다는 뜻이다.

 

특정 니니즈 수를 탐색할 때마다 stones를 순회해야 하므로 최종 시간 복잡도는 (이분탐색 x stones 순회), 즉 O(nlogm)이 된다.

n의 범위가 10^5이므로 이분탐색 풀이를 선택하면 효율성까지 정답으로 처리된다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool check(int mid, vector<int> stones, int k) {
    
    //mid-1까지 징검다리를 건넜을 때 상태
    int sz = stones.size();
    for (int i=0; i<sz; i++)
        stones[i] = max(0, stones[i]-(mid-1));
    
    //연속하는 0의 개수가 k개 초과 이면 false 리턴
    int idx = 0;
    while (idx < sz) {
        if (stones[idx]) idx++;
        else {
            int cnt = 0;
            while (idx < sz && !stones[idx]) {
                cnt++;
                idx++;
            } 
            if (cnt+1 > k) return false;
        }
    }
    return true;
}

int binarySearch(const vector<int>& stones, int k) {
    
    int first = 1;
    int last = 200000000;
    int ret = 1;
    
    while (first <= last) {
        int mid = (first+last)/2;
        if (check(mid, stones, k)) {
            ret = mid;
            first = mid+1;
        }
        else last = mid-1;
    }
    return ret;
}

int solution(vector<int> stones, int k) {
    
    return binarySearch(stones, k);
}