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

문제 링크

징검다리 건너기

풀이

슬라이딩 윈도우와 deque를 이용하는 문제. 조금 어렵네 ...
k사이즈의 부분 배열에서 가장 큰 값들 중 가장 작은 수가 답이 된다.
1. 일단 deque가 비어있거나, 맨 뒤 원소 값이 현재 집어 넣을 원소 값보다 크면 pop은 하지 않고 현재 원소를 push한다.
1-1. 그렇지 않으면 맨 뒤 원소 값이 현재 집어 넣을 원소 값보다 클 때까지 pop_back 한다.
2. 윈도우의 범위가 아니면 맨 앞 원소를 pop 한다.
3. 윈도우의 범위가 k일 때만 계산해주기 위해 앞 부분은 answer에 갱신해주지 않고, 나온 값들 중에서(deque의 맨 앞 값은 항상 그 범위의 제일 큰 값이다) 작은 값을 갱신한다.

코드

#include <string>
#include <vector>
#include <deque>
#include <iostream>
#define INF 200000001

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = INF;
    
    deque<pair<int,int>> dq; // 징검다리와 인덱스
    
    for(int i=0;i<stones.size();i++)
    {
        if(dq.front().second<=i-k) dq.pop_front(); // 윈도우 범위가 아니면
        while(1)
        {
            if(dq.empty()) break;
            if(dq.back().first>stones[i]) break;
            dq.pop_back(); // dq의 맨 뒤 원소가 추가된 원소보다 작으면 pop
        }
        dq.push_back({stones[i],i});
        
        if(i<k-1) continue;
        answer = min(answer, dq.front().first);
    }
    
    return answer;
}