백준 11003번 최소값 찾기

문제 링크입니다: https://www.acmicpc.net/problem/11003

세그먼트 트리 알고리즘을 통해 풀어도 되고 슬라이딩 윈도우 기법을 통해 풀어도 되는 문제였습니다.

저는 슬라이딩 윈도우 기법을 이용하여 풀었습니다.

알고리즘은 아래와 같습니다.

1. 배열을 입력 받습니다.

2. pair<int, int> 형 덱(deque)에 숫자와 인덱스를 저장하는데 범위가 (i - L + 1) ~ i 사이에 있는 숫자들에 대해서 최소값을 찾아야하므로 덱에는 최대 L개의 숫자만 저장되어있습니다.

3. 덱에 있는 숫자들은 오름차순으로 정렬되어 있고 arr[i]가 덱에서 제일 큰 숫자가 되도록 덱을 조정합니다.

4. 각 인덱스마다 덱의 제일 앞에 있는 숫자를 출력해줍니다.

->오름차순 정렬이므로 해당 범위 내에 최소 숫자입니다.

#include <iostream>

#include <deque>

using namespace std;

 

const int MAX = 5000000;

 

int arr[MAX];

deque<pair<int, int>> dq; //value, idx

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int N, L;

        cin >> N >> L;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        for (int i = 0; i < N; i++)

        {

                 //dq에는 최대 L개의 값이 저장

                 if (!dq.empty() && dq.front().second <= i - L)

                         dq.pop_front();

                 //arr[i]가 덱 내에서 제일 큰 숫자

                 while (!dq.empty() && dq.back().first > arr[i])

                         dq.pop_back();

 

                 dq.push_back(make_pair(arr[i], i));

                 cout << dq.front().first << " ";

        }

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~