[c++] 백준 11003 - 최솟값 찾기(deque)

0. [c++] 백준  -

https://www.acmicpc.net/problem/11003

1. 풀이

deque에 pair로 숫자를 저장하는 것이 포인트였다.

deque에 수를 넣을 때, 자신의 크기와 자신의 위치를 한꺼번에 집어넣고, 수의 진입 방법은 오름차순을 유지할 수 있도록 한정시켜서 수를 넣어주었다.

결과적으로 deque.front()값은 항상 최솟값을 유지하게 되고, 답을 구해낼 수 있었다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include<iostream> #include<deque>   using namespace std;   const int MAX = 5000001;   deque<pair<int, int> > dq;   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N, L, temp;     cin >> N >> L;     for (int i = 0; i < N; i++) {         cin >> temp;           if (!dq.empty() && dq.front().second <= i - L)             dq.pop_front();           while (!dq.empty() && dq.back().first > temp)             dq.pop_back();           dq.push_back({ temp, i });         cout << dq.front().first << " ";     } } Colored by Color Scripter

cs

3. 참고

https://jaimemin.tistory.com/746

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!