[프로그래머스 징검다리 건너기] c++ (풀이,코드,이분탐색)

문제링크

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

프로그래머스

 

문제

 

풀이, 코드(이진탐색)

 

이 문제는 풀때 어떤 알고리즘이다!

 

라는 생각이 아니고 처음 풀때는 아주 뇌를 비우고 풀었었습니다..

 

경우의 수도 생각없이 그냥 뭐 일단 가장 적은값에 대해서 다 빼버리고 그다음에 탐색을 순차접근을 하면 되지 않을까 하는 생각으로 뇌를 비우고 아래의 코드처럼 짰었습니다.

 

틀린 이상한 코드

#include <string>

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

int check(vector<int> stones,int idx, int k){

    for(int i = idx;i < stones.size() && i <= idx + k;i++){

        if(stones[i] >= 1)

            return i - idx;

    }

    return -1;

}

int solution(vector<int> stones, int k) {

    int answer = 0;

    int minValue = 200000000;

   

    //최솟값을 찾고 최솟값만큼 다 빼주고 시작을 할 예정

    for(int i = 0; i < stones.size();i++){

        if(stones[i] < minValue){ //이렇게하면 최솟값

            minValue = stones[i];

        }

    }

    for(int i = 0; i < stones.size();i++){

        stones[i] -= minValue;

    }

    answer += minValue; //일단 숫자들만큼 다 뺌

   

    while(1){

        int step = 0;

        for(int i = 0; i < stones.size();i++){

            if(stones[i] >= 1){

                step = 0;

                stones[i] -= 1;

            }else{

                step++;

            }

            if(step >= k)

                return answer;

        }

        answer++;

    }

}

바로 효율성에서 개박살나야지 너!!

 

이렇게 되면  최악의 경우 200000 * 200000000까진 아니더라도 이런 슬픈 현실에 마주할지도 모릅니다.

 

하나씩 빼는 것이 아닌 이분탐색을 이용하여 진행하였습니다.

 

1.이분탐색을 이용하기 위해 시작지점과 끝지점을 선언하여 이분탐색을 진행하였습니다.

단, 여기서 이분탐색의 경우 백터에서 가장 큰값을 기준으로 진행을 하였습니다.

 

2. 건널수 있는 경우 mid + 1 건널 수 없는 경우 mid -1으로 진행

 

3. 갱신을 해주는데 answer < mid라면 mid = answer로 갱신을 시켜줍니다.

 

맞은 코드

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int search(vector<int> stones, int mid, int k){

    int cnt = 0;

    for(int i = 0; i < stones.size();i++){

        if(stones[i] < mid)

            cnt++;

        else

            cnt = 0;

        if(cnt >= k) return -1;

    }

    return 1;

}

int solution(vector<int> stones, int k) {

    int answer = 0;

    int start = 0;

    int end = *max_element(stones.begin(),stones.end());

   

    while(start <= end){

        int mid = (start + end) / 2;

        if(search(stones,mid,k) == 1){

            start = mid + 1;

            if(answer < mid)

                answer = mid;

        }else

            end = mid -1;

    }

    return answer;

}

 

이분탐색에 대해서 기억은 나지만 안푼지도 꽤 됐고 익숙치 않아서 정말 사경을 해매는 느낌으로 어떻게든 했네요..