프로그래머스 - 징검다리 건너기(C++)

 문제를 보고 든 생각은 이번에도 구현보다는 효율성 문제겠구나 싶었다. 

 

https://school.programmers.co.kr/learn/courses/30/lessons/64062

 

첫번째 생각 : 한 번씩 돌려보면서 -1 하고 돌이 0이되면 0의 갯수확인

-> 당연히 시간초과다. 돌의 최대가 2억이다.

 

두번째 생각 : 주어진 배열을 오름차순으로 정렬한다. 그리고 0번부터 n번까지 돌려보며 0의 갯수를 확인한다. 이때 첫번째와 달리 정렬된 0번부터 바로 stones를 0으로 정해서 숫자를샌다. 이러면 시간복잡도가 O(N^2) 이기때문에 정확도테스트에선 통과하지만 효율성 테스트를 한개도 통과할 수 없다.

 

세번째 생각 : 드디어 이분탐색이 떠올랐다. "어 설마.." 하면서 생각은 났지만 구체적으로 구현방법이 떠오르지는 않았다. 정리해보면 먼저 두번째 풀이에서 사용한 솔루션을 함수로만든다. 0부터 N까지 돌려보지 않기 때문에 함수 자체의 시간 복잡도는 O(N)이다. 그 후 mid값부터 검사해서 true(징검다리를 건널 수 없음)이면 왼쪽으로, false(아직 징검다리를 건널 수 있음) 이면 오른쪽으로 보낸다. 이렇게 하면 O(NlogN)으로 풀이할 수 있다. 

 

이분탐색을 빨리 떠올렸으면 한시간.. 정도면 풀었을 것 같다.

lower_bound를 구해야하는 것 같기도한데 이분탐색을 다시 한번 확실하게 잡고가야할 것 같다. 그리고 카카오 문제들은 구현이 어렵거나 구현은 쉬운데 효율성 때문에 알고리즘을 써야하는 문제로 나뉘는 것 같다. 당연한소린가..

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool sol(vector<int> arr, int N, int target){
    int cnt = 0;
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] <= N){
            cnt++;
            if(cnt == target)
                return true;
        }
        else
            cnt = 0;
    }
    return false;
}

int solution(vector<int> stones, int k) {
    int answer = 10000000000;
    vector<int> temp = stones;
    
    sort(temp.begin(), temp.end());

    if(stones.size() == k)
        return temp[stones.size() - 1];
    
    int hi = stones.size();
    int lo = 0;
    bool check = false;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        //cout << mid << endl;
        if(sol(stones, temp[mid], k)){
            answer = min(answer, temp[mid]);
            //cout << mid << " " << temp[mid] << endl;
            hi = mid - 1;
        }else{
            lo = mid + 1;
        }   
    }
    
    return answer;
}

 

이분탐색을 써도 18ms... 더 최적화 시킬 수 있는건가?