programmers 징검다리 건너기

programmers 징검다리 건너기 : programmers.co.kr/learn/courses/30/lessons/64062

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

 

2019 카카오 개발자 겨울 인턴십 level3의 징검다리 건너기 문제입니다.

 

정확도와 효율성을 동시에 따지는 문제라는 것은 뭔가 알고리즘이 존재한다는 의미입니다.

 

정확성만 따지자면 2중 포문으로 k개에 대해서 모든 경우를 구하는 것인데,

징검다리의 수가 20만개에 원소의 값들은 2억이라서 효율성 점수를 얻는데는 실패할 것입니다.

 

저는 건널 수 있는 최대 값이 k라는 것에서 힌트를 얻어 이분탐색에 접근하였습니다.

 

현재 예시를 보겠습니다.

 

stones                                           k                                                 result

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

3

3

 

만약 친구 3명이 징검다리를 건넌다면? 

0 1 2 0 0 0 1 0 2 0 이라는 값이 됩니다.

0 0 0 이 3번 반복됩니다.

한번에 건너뛸 수 있는 k의 값이 3이라고 주어져 있습니다.

이는 인덱스2 부터는 3칸을 한번에 뛰어넘을 수 없다는 소리가 됩니다.

즉 => 3명까지는 징검다리를 건넜고, 4번째 친구부터는 징검다리를 못건넌다는 얘기입니다.

 

만약 친구 4명이 징검다리를 건넜다고 해도

3명이 건넜을 때 처럼

0 1 2 0 0 0.. 에서 0이 3번 반복되는 구간을 찾을 수 있습니다.

즉 0 이 k번 반복되는 구간이 있다는 것으로부터 저는 아래와 같은 생각을 하였습니다.

'현재 인원보다 많은 인원이 징검다리를 건널 수는 없다' 는 것이고

'현재 인원도 사실은! 징검다리를 건널 수 있는지 없는지는 모른다' 는 것이기 때문에 

'현재 인원이 일단 정답이라고 생각하고, 혹시 못 건널수도 있으니까 인원을 줄여보자!' 입니다.

 

코드는 아래와 같습니다.

 

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

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

int solution(vector<int> stones, int k) {
    
    int left = 1;
    int right = 200000000;
    int mid;
    while(left < right){
        mid = (left+right)/2;
        
        if(checkCross(stones, k, mid)){
            left = mid + 1;
        }
        else{
            right = mid; // 이 인원까지는 뛸 수 있을지 모른다. 줄여나가보자!
        }
    }
    
    return right;
}