프로그래머스] 징검다리 건너기- c++

2019 카카오 개발자 겨울 인턴십 5번 문제 징검다리 건너기

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

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

 

IDEA의 흐름 

1. 보자마자 될 때까지 while 문 돌면서 stones에서 하나씩 빼주면 되지 않나? 라고 생각하고 돌려봤지만 역시나 실패! 

사실 돌려보지않고 제한사항만 봐도 알 수 있다. stones의 원소 값 200,000,000 이니까,,, 단순 반복문은 안될 거라고 생각했다. 그러면 이제 $N^{2}$이 아니라 NlogN으로 갈 수 있는 방법이나 N으로 갈 수 있는 방법을 찾아야 한다.

 

2. 혹시 k값 이하로 연속하는 수열의 개수를 찾으면 되나? -> 그런 규칙이 아니다.

 

3. 반복적으로 찾으면서 시간복잡도가 NlogN인 거 뭐 있지? => 이분탐색

연속된 숫자를 찾아야한다. 징검다리 숫자는 아니고 ,,,,  징검다리 값에서 뺴줄 값들이 연속이다. 

start = 1 , end = 징검다리의 최댓값으로 설정

for문을 돌면서 mid 값을 빼준다. 이 때, 연속해서 0 이하가 나오는 개수를 카운팅해주고 가장 긴 구간을 저장해준다.

가장 긴 구간이 k보다 크다 -> 너무 많이 뺐다는 뜻 -> 작은 쪽으로 땡기자 -> end = mid-1

가장 긴 구간이 k보다 작다 -> 더 빼도 된다는 뜻 -> 큰 쪽으로 땡기자 -> start = mid + 1

 

CODE

#include<iostream>
#include <string>
#include <vector>
#include<algorithm>
///10:05- 10:55
using namespace std;

int solution(vector<int> stones, int k) {
    int end = *max_element(stones.begin() , stones.end());
    int start = 1;
    while(start<=end){
        int mid = (start + end)/2;
        int max_conti = 0;
        int conti = 0;
        for(int i=0;i<=stones.size();i++){
            if(i == stones.size()){
                max_conti = max(max_conti , conti);
                continue;
            }
            if(stones[i]-mid < 1) conti++;
            else {
                max_conti = max(max_conti , conti);
                conti = 0;
            }
        }
        if(max_conti >= k) end = mid -1;
        else start = mid + 1;
    }
    return start;
}

 

 

후기

이분탐색 너무 오랜만에 본다. 삼성에는 그런 문제가 안나오니까 최근에 거의 안풀었었는데, 카카오에는 나오는 거 같다.

카카오 기출 유형? 알고리즘? 을 좀 검색해서 주말 동안 유형 위주로 풀어봐야겠다.