[프로그래머스 Lv3] : 징검다리 건너기

문제 링크

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

프로그래머스

내구도가 정해진 징검다리가 있을 때, 건너갈 수 있는 니니즈 친구들의 수의 최대를 리턴하자.

 

풀이

직접 한 명, 한 명 건너가면서 돌의 내구도를 감소시키면 물론 정답은 출력이 될 것이다. 하지만 효율성 테스트에서 시간초과가 나게 된다.

그래서 내가 처음 생각했던 방법은

내구도가 0인 돌이 연속해서 K개 이상 있을 때, 그때는 더 이상 사람이 건너가지 못하게 된다.

그래서 다리를 K개씩 나눠서 봤을 때, K개의 다리 중 내구도가 가장 큰 다리의 내구도만큼 사람이 지나가면 K개의 징검다리는 모두 0이 된다.

K개씩 나눠서 봤을 때, 구간의 최대값들 중 최소값이 건너갈 수 있는 사람의 수의 최대가 된다.

 

이렇게 코드를 짰을 때, 대부분의 테스트 케이스에서 통과하지만 효율성 테스트에서 시간초과가 났다.

 

보통 이렇게 큰 범위의 숫자가 주어졌을 때, 우리는 이분탐색을 사용한다.

건너갈 수 있는 최소 사람의 수는 1일 것이고, 최대는 징검다리들의 내구도 중 최대값이 될 것이다.

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

이때 건너갈 사람의 수를 mid값으로 선정한다.

만약 mid만큼의 사람이 건너갔다고 했을 때, 연속된 0이 K개 미만으로 나온다면 mid만큼의 사람이 건너가도 문제가 없다는 뜻이다.

반대로 mid만큼 건넜다고 가정했을 때, 연속된 0이 K개 이상이 나오면 그때의 mid는 유효하지 않은 값이 된다.

연속으로 등장하는 0의 길이 중 최대값을 Max_zero라고 한다면

        if(Max_zero >= k)
            R = mid - 1;
        else{
            answer = max(answer, mid);
            L = mid + 1;
        }

위의 식을 따라 이분탐색을 진행한다.

 

코드 작성

#include <bits/stdc++.h>
using namespace std;
 
int solution(vector<int> stones, int k) {
    int answer = 0;
    int L = 0; int R = *max_element(stones.begin(), stones.end());
    
    while(L <= R){
        int mid = (L + R) / 2;
        int zero = 0;
        int Max_zero = 0;
        for(int i = 0; i< stones.size(); i++){
            if(stones[i] - mid < 0)
                zero++;
            else{
                Max_zero = max(Max_zero, zero);
                zero = 0;
            }
        }
        Max_zero = max(Max_zero, zero);
        
        if(Max_zero >= k)
            R = mid - 1;
        else{
            answer = max(answer, mid);
            L = mid + 1;
        }
    }
    return answer;
}