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

문제

---

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

풀이

---

주어진 징검다리 배열에서 각 원소 값을 1 빼는 것을 반복할 때, 0이 k개 이상 연속되지 않는 최대 횟수를 구하는 문제이다. 단순하게 각 원소 값들을 빼주는 것은 최대 원소 값 200,000,000 이하, 배열의 크기 200,000 이하라는 조건으로 인해 시간 초과가 발생한다. 따라서 이를 해결하기 위해 순차적으로 묶어 탐색한다. 배열의 원소를 순차적으로 k개씩 묶었을 때 각 최댓값은 구간 내 나머지 값들이 모두 0이 되어도 0이 k개 이상 연속되지 않으므로, 이러한 최댓값 중 가장 작은 값이 0이 k개 이상 연속되지 않는 최대 횟수이다. 이를 Deque를 통해 k 이하의 거리를 가진 원소들 중 최댓값을 추가하고 최댓값보다 낮은 숫자를 제거한다.

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

using namespace std;

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

    vector<int> ans;

    int idx = 0;
    deque<int> iter;
    deque<int> iter_idx;

    for (int i = 0; i < stones.size(); i++)
    {
        if (iter.size() == 0)
        {
            iter.push_back(stones[i]);
            iter_idx.push_back(i);
        }

        else
        {
            if (i - iter_idx[0] >= k)
            {
                iter.pop_front();
                iter_idx.pop_front();
            }

            int cnt = iter.size();

            for (int j = 0; j < cnt; j++)
            {
                if (iter[iter.size() - 1] < stones[i])
                {
                    iter.pop_back();
                    iter_idx.pop_back();
                }

                else break;
            }

            iter.push_back(stones[i]);
            iter_idx.push_back(i);

        }

        if (i >= k - 1) ans.push_back(iter[0]);
    }

    answer = *min_element(ans.begin(), ans.end());


    return answer;
}