[프로그래머스]2019 카카오 개발자 겨울 인턴십 : 징검다리 건너기 (level 3) (c++)

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

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

 

이분탐색

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 200000000;

bool check(vector<int> &stones, int k, int passed)
{
    // 왼쪽 땅부터 시작
    int last_idx = -1;
    for (int i = 0; i < stones.size(); ++i)
    {
        // 건널 수 있는 디딤돌이면
        if (stones[i] - passed >= 0)
        {
            // 마지막 디딤돌간의 간격이 k초과이면 false
            if (i - last_idx > k)
            {
                return false;
            }
            last_idx = i;
        }
    }

    // 오른쪽 땅까지의 거리가 k이하면 true
    return (stones.size() - last_idx <= k);
}

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

    // stones 요소 중 최소값/최대값 구하기
    int left = MAX;
    int right = 0;
    for (int stone : stones)
    {
        left = min(stone, left);
        right = max(stone, right);
    }

    /*
        이분탐색
        조건을 만족하는 디딤돌 숫자 중 최대값 구하기
    */
    int answer = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;

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

    return answer;
}

 

문제의 규칙을 정리하면 다음과 같다.

- 밟은 디딤돌은 숫자가 1씩 줄어든다.
- 0 이하의 디딤돌은 밟을 수 없다.
- 밟을 수 있는 바로 다음 디딤돌을 밟는다.
- 밟을 수 있는 디딤돌 간의 간격이 k이하가 되어야 한다.

 

이 문제 풀이의 힌트는 제한사항에 있다.

- 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
- stones 배열의 크기는 1 이상 200,000 이하입니다.
- stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
- k는 1 이상 stones의 길이 이하인 자연수입니다.

 

먼저 stones배열을 순회하며 매번 0이 아닌 최소의 숫자 m을 구한 다음,

stones 수열에서 m씩을 뺀다고 하자.

이는 O(N^2)의 시간복잡도라서 O(40,000,000,000)이 되어버리기 때문에 시간초과가 난다.

 

따라서 stones배열을 순회하는 전략은 쓸수가 없고,

이분탐색으로 조건을 충족하는 최대의 원소값을 찾는 전략을 써야 한다. 

그러면 O(log M) * O(N)의 풀이가 가능하다. 

 

조건 충족여부를 체크할 때, 디딤돌에서 양 끝의 땅까지의 거리도 체크해야한다!