[Algorithm] Programmers :: 징검다리 건너기

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

프로그래머스

unordered_map<int, int> check;
 
int solution(vector<int> stones, int k)
{
    int answer = 0;
 
    if (stones.size() == k)
    {
        return *max_element(stones.begin(), stones.end());
    }
 
    priority_queue<int> maxNums;
 
    for (int i = 0; i < k; ++i)
    {
        maxNums.push(stones[i]);
        check[stones[i]]++;
    }
 
    stones.push_back(200000001);
 
    for (int i = k; i < stones.size(); ++i)
    {
        while (check[maxNums.top()] == 0)
        {
            maxNums.pop();
        }
 
        int prevMaxNum = maxNums.top();
        stones[i] = min(prevMaxNum, stones[i]);
        maxNums.push(stones[i]);
 
        ++check[stones[i]];
        --check[stones[i - k]];
    }
 
    return stones.back();
}

 

i번째 인덱스에 위치한 돌에 올 수 있는 최대인원수는

min(max(stones[i-k] ~ stones[i-1]), stones[i])

라는 규칙을 발견할 수 있었습니다.

 

해당 돌이 0이더라도 k만큼은 건너뛸 수 있기 때문에, i-k부터 i-1까지는 i번째로 건너뛸 수 있습니다.

즉, i-k부터 i-1의 인덱스들은 i로 건너올 수 있는 후보들이기 때문에 가장 큰값을 i번째와 비교합니다.

i번째의 숫자값만큼만 사람이 건너올 수 있기 때문에, 이전의 가장큰값과 i번째의 값들 중 '작은 값'을 기록합니다.

 

여기서 중요한 건 특정구간의 최대값을 어떻게 저장하고 있느냐입니다. i-k ~ i-1의 최대값을 최대한 빠르게 구해야하는게 관건입니다. 단순히 해당구간만큼 반복돌면서 최대값을 구하면 시간제한에 걸리기 때문에(k가 10만이란 가정하에 10만 * 10만 시간복잡도가 됩니다) 좀 더 효율적인 방법으로 i-k ~ i-1의 최대값을 구해야 합니다.

 

저는 값들을 우선순위큐에 보관해서 꺼내는 식으로 하되, 다음 인덱스로 넘어가면 이전의 i-k번째 인덱스의 값은 범위에서 빠지기 때문에 빠졌다는 표시를 map에다가 했습니다.

그래서 검사할 때 map에 해당값을 살펴봤을 때 0이라면, 즉 우선순위큐에 존재하지 않는 값이라면(i-k ~ i-1번 구간에 없는 값이라면) 빼버리고 다음 큰값을 검사하는식으로 했습니다.

시간효율은 아래와 같이 나왔습니다.

 

통과는 했지만, 조금 찝찝해서 다른사람풀이를 보니 이분탐색으로 풀었다는걸 알 수 있었습니다.

사실 처음 문제를 봤을때도 단순시간복잡도가 값이 커서 이분탐색풀이가 있을수도 있다는걸 생각하긴 했지만, 이런 문제는 일단 슬라이딩윈도우와 관련된 풀이법이 먼저 생각나서 위에 했던것처럼 풀었었습니다.

 

아래는 이분탐색 풀이입니다.

 

 
bool isPossible(int mid, int k, vector<int>& stones)
{
    int count = 0;
 
    for (int i = 0; i < stones.size(); ++i)
    {
        if (stones[i] - mid < 0) ++count;
        else count = 0;
 
        if (count == k) return false;
    }
 
    return true;
}
 
int solution(vector<int> stones, int k)
{
    int answer = 0;
    int left = 1;
    int right = 200000001;
    
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (isPossible(mid, k, stones))
        {
            left = mid + 1;
            answer = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
    
    return answer;
}

 

최대건널수 있는 사람수를 고정으로 해둔 후, 해당 사람수가 실제로 징검다리를 건널 수 있는지에 대한 여부만 판단해서 점점 범위를 좁힙니다.

건널수 있는지에 대한 여부를 어떻게 아느냐? 가 중요합니다.

처음부터 순회하면서, stones[i] - mid값이 음수인값이 k개만큼 연속되는지만 체크하면 됩니다.

즉 아무구간에서나 음수인값이 k개만큼 연속되어진다면, 해당 인원으론 절대 징검다리를 건널 수 없습니다.

최대 k만큼만 점프할 수 있기 때문입니다.

 

이분탐색으로 풀었을 시 효율성은 압도적으로 좋아졌습니다..