C++:: 프로그래머스 < 징검다리 건너기 >

얼핏 deque를 사용하여 푸는 방법을 구상했지만 제대로 로직을 구현하지 못한 문제이다. 잘푼 풀이를 참조한다.
해당 풀이의 핵심은 dq에 쌓아가면서 맨앞에 있는 징검다리의 인덱스가 현대 인덱스 - (k-1) 한 인덱스보다 작지 않을때 까지 dq를 갱신해주고,
dq의 뒷부분 징검다리가 현재 징검다리보다 작지 않을때까지 갱신해주는 것이다.
정답은 dq의 맨앞 징검다리 크기들중 제일 작은 값이다.

#include <string>
#include <vector>
#include <deque>
using namespace std;
 
int solution(vector<int> stones, int k) {
    int answer = INT32_MAX;
    deque<pair<int, int>> dq;
 
    for (int i = 0; i < stones.size(); i++) {
        while (!dq.empty() && dq.front().second < i - (k - 1)) {
            dq.pop_front();
        }
        while (!dq.empty() && dq.back().first < stones[i]) {
            dq.pop_back();
        }
        dq.push_back(make_pair(stones[i], i));
        if (i >= k - 1 ) answer = min(answer, dq.front().first);
    }
    return answer;
}