[2019 카카오 개발자 겨울 인턴십 코딩테스트] 문제5. 징검다리 건너기

 

문제풀이

 

이진 탐색을 활용한 문제

개인적으로는 아이디어 구현까지 나름 모의 코테 문제 중에서는 가장 시간을 많이 투자한 문제였습니다.

 

이진 탐색의 마지막 처리가 헷갈려 시간을 좀 쏟았습니다.

문제 범위 때문에 순차적으로 하나씩 제쳐나가면 시간 초과가 뜨기 때문에 이진 탐색을 활용해야 됩니다.

 

소스코드

#include <string>
#include <vector>
#include <iostream>
#define STONE_MAX_VAL 200000000
using namespace std;
 
 
bool isSuccess(int mid, vector<int> stones, int k) {
    int cnt = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - mid <= 0) {
            cnt++;
            if (cnt >=k)
                return false;
        }
        else {
            cnt = 0;
        }
    }
    return true;
}
 
int  binary_search(vector<int> stones, int k) {
    int start = 0;
    int end = STONE_MAX_VAL;
    int mid;
    while (start <end) {
        //cout << start << "," << end << endl;
        if (start+1 == end) {
            if (isSuccess(end-1, stones, k)) {
                return end;
            }
            return start;
        }
        mid = (start + end) / 2;
        if (isSuccess(mid-1, stones, k)) {
            //cout<<"!!"<<endl;
            start = mid;
        }
        else {
            end = mid - 1;
        }
    }
    return start;
}
 
int solution(vector<int> stones, int k) {
 
    long long result = binary_search(stones, k);
    //cout<< result <<endl;
    if (result == -1)
        return 0;
    return result;
 
}
int main() {
    //cout << solution({ 2,4,5,3,2,1,4,2,5,1 }, 3) << endl;
    cout << solution({ 0 }, 1) << endl;
}

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스