[11003번] 최소값 찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Deque

2. 슬라이딩 윈도우

덱의 구성을 오름차순으로 계속해서 만들어 주면 된다.

그렇게 된다면 계속해서 최솟값이 들어가게 될 것이고 

아래 슬라이딩 윈도우 알고리즘을 통해 빠지기 전까지 계속해서 최솟값을 유지해 줄 수 있게 된다.

정답은 vc에 담아서 출력하거나, 그냥 vc.push_back부분에서 printf를 바로 해도되긴 한다.

소스 코드 : 

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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <cstdio> #include <queue> #include <vector>   using namespace std;   int arr[5000003]; vector<int> vc;   int main() {     int n, l;     scanf("%d %d", &n, &l);       deque <int> dq;       for (int i = 1; i <= n; i++)     {         scanf("%d", &arr[i]);           // 덱이 비어있다면         if (dq.empty())             dq.push_back(arr[i]);           // 덱에 값이 있다면         else         {             // 덱의 마지막 값이 현재 arr값보다 크면 계속 빼준다.(필요없음)             while (!dq.empty() && dq.back() > arr[i])                 dq.pop_back();               // 현재 값을 넣어준다.             dq.push_back(arr[i]);         }           // i > l이 되는 순간 덱 앞의 값과 i-l번째의 arr[i-1]가 같다면          // (슬라이딩 윈도우 기법)         if (i > l)             if (dq.front() == arr[i - l])                 dq.pop_front();           vc.push_back(dq.front());     }       for (int i = 0; i < n; i++)         printf("%d ", vc[i]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus