[2019 kakao winter internship] 05. 징검다리 건너기(cpp/python)

징검다리 건너기

프로그래머스

문제 설명

건널 수 있는 사람 수를 기준으로 1 ~ max(stones) 에 대한 이분탐색을 하여 stones 값들을 mid 값 만큼 갂아 건널 수 있는지 확인하여 그 때의 최소값을 찾는 문제이다.

문제 풀이

소스코드 : C++

1. left =1 , right = stones의 최대값으로 초기화하고 이분탐색에 진입한다.
2. mid = (left + right)/2로 놓고, 건널 수 있는 mid값보다 작거나 같은 경우를 세는 cnt=0 으로 놓는다.
3. cnt>k되면 건널 수 없는 경우이므로 cnt>=k가 될 때 flag = true로 놓고 break를 건다.
4. 만약 flag = true 즉, 건널 수 있는 경우를 찾았다면 그 보다 작은 값으로 건널 수 있는 경우를 다시 탐색하기 위해 right = mid-1을 해준다.
5. 그렇지 않다면 즉, 건널 수 있는 경우를 찾지 못했다면 그 보다 큰 값으로 건널 수 있는 경우를 다시 탐색하기 위해 left = mid+1 을 해준다.
6. 위 과정을 left > right 될 때까지 반복하여 탐색하여 left 값을 반환해준다.

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solution(vector<int> stones, int k) {
    int left = 1, right = *max_element(stones.begin(),stones.end());
    int size = stones.size();
    while(left <= right){
        int mid = (left + right) / 2;
        int cnt = 0;
        bool flag = false;
        for(int i = 0; i < size; i++){
            //cnt가 연속으로 1씩 더해져 k보다 크거나 같아지는 경우에는 건널 수 없음.
            if(stones[i] - mid <= 0) cnt++;
            else cnt = 0;
            if(cnt >= k){
                flag = true;
                break;
            }
        }

        if(flag) right = mid - 1;   // mid값 보다 더 작은 경우가 있는지 재 탐색
        else left = mid + 1;        // mid값에 대한 경우를 찾을 수 없으므로 더 큰 값 탐색
    }
    return left;
}
int main(){
    // vector<int> s = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
    vector<int> s = {4,5,6};
    int k = 2;
    cout << solution(s, k) << endl;
    return 0;
}

소스코드 : Python

def solution(stones, k):
    left =1
    right = max(stones)
    while left <= right:
        mid = int((left + right)/2);
        cnt = 0
        flag = False
        for st in stones:
            if st - mid <=0: cnt+=1
            else: cnt = 0
            if cnt >= k:
                flag = True
                break

        if flag: right = mid -1 
        else: left = mid +1
    return left

처음에는 연속하는 수열에 사로잡혀 ({1,2,3} , {3,2,1}과 같은 경우) 그 경우에 대하여 건널 수 있는 최소값을 찾으며 O(N) 만에 찾아내려고했지만 접근 자체가 틀렸다. k=5 이고 {7,1,2,1,7} 이런 경우 답은 2가 나와야하지만 연속하는 수열을 찾아 계산하면 연속하는 수열의 길이가 5인 경우도 없을 뿐더러 그 경우를 처리한다고 해도 7이 나와버리므로 답은 틀린다.

하나에 사로잡혀버려서 많은 시간을 낭비하고 다른 풀이를 참고하여 풀었다. 이분탐색에 너무 약한 것 같다... 이분탐색 문제를 좀 더 풀어봐야겠다.