[1일 1알고] 징검다리 건너기

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

프로그래머스

차례대로 건너가며 디딤돌의 내구도를 감소시킵니다.

이 때 k를 넘는 칸을 한번에 뛸 수 없기 때문에 이를 처음으로 만족하는 값을 찾는 것이 문제입니다.

 

이번 문제는 조건을 보면 배열의 크기가 20만 이하이며 원소가 2억이하이기 때문에 

매번 시뮬레이션을 실시한다면 시간을 충족하지 못할 것임을 바로 알 수 있습니다.

 

그렇기 때문에 1부터 시작해서 감소시켜가며 계산할 수는 없습니다.

 

다행히도 원소의 크기는 최대 2억이지만 배열의 크기가 20만이기 때문에 이분탐색을 이용하면 대충 20만 * 28정도가 최대 계산이겠네요 충분해보입니다.

---

// 징검다리 건너기
// 디딤돌의 숫자는 밟으면 줄어듬
// 0이라면 밟지 못하고 건너 뜀
// 배열의 크기는 20만 이하
// 원소 값은 2억 이하 
bool canCross(vector<int>& stones, int k, int people)
{
    int zeroCount = 0;

    for (int stone : stones)
    {
        if (stone <= people)
        {
            zeroCount++;
            if (zeroCount >= k)
                return false;
        }
        else
        {
            zeroCount = 0;
        }
    }

    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;

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

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (canCross(stones, k, mid))
        {
            answer = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return answer;
}

결론적으로 코드 자체는 간단합니다.

 

left는 디딤돌의 최솟값인 1, right는 배열의 원소 중 가장 큰 값으로 하고

하던대로 이분탐색을 돌리면됩니다.

 

mid값에 대해 건널 수 있는 상황인지 확인하고,

건널 수 있다면 더 큰 값에 대해 탐색하고 없다면 더 작은 값에 대해 탐색합니다.