[프로그래머스 2019 카카오 개발자 겨울 인턴십] 징검다리 건너기

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

ㅎㅎ.. 새로운 문제가 나오면 전혀 접근을 못하는게 문제다.

문제의 접근법에 대해 공부해야 할 것 같다.

 

이중 포문을 돌려도 문제가 해결가능하지만 시간복잡도가 n^2이다.

for int i=1; i<INF; i++

  for int j=1; j<stones.size(); j++

    0의 개수 세기

  0이 k개 이상이라면 break

 

이렇게 하면 n^2이다.

 

그래서 다른 접근법을 찾아야 한다. 

선형 자료구조에서 arbitrary한 특정값을 찾는 것이므로 이분탐색을 사용한다.

이분 탐색을 사용하면 시간 복잡도가 logN이므로

n * log n이 된다.

 

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

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    int start = 1, end = 200000000;
    while(start<=end){
        int mid = (start + end)/2;
        
        bool flag = true;
        int cnt=0;
        for(auto a: stones){
            if(a-mid <=0){
                cnt++;

            }else {
                cnt=0;
            }

            if(cnt >= k){
                flag = false;
                 break;
            }
        }
        
        if(!flag){
            end = mid-1;
        }else {
            start = mid+1;
        }
    }
    answer = start;
    return answer;
}