[백준/BOJ] 백준 11003번 : 최솟값 찾기

www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

deque<pair<int, int>> temp; 에 구간의 (값, 인덱스)를 저장한다 그리고 구간을 돌면서 구간 밖의 인덱스 인것들은 temp에서 제거하고, 또한 이제 들어오는 수 보다 크거나 같은 수들은 temp에서 제거한다 즉 이제 들어오는 수로 인해 앞으로 최솟값이 될 수 없는 수들을 제거하는 것이다. 그리고 이제 들어오는 수를 넣는다. 그러면 temp의 가장 앞에 있는 수는 구간의 최솟값이 된다는 것을 이용해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
using namespace std;

int n, l;
vector<int> a(5000001, 0);
deque<pair<int, int>> temp; //(값,인덱스)저장
vector<int> result;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> l;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		a[i] = input;
	}

	for (int i = 1; i <= n; i++)
	{
		int left_point = i - l + 1;
		int right_point = i;

		while (temp.size() != 0)
		{
			//구간 밖의 인덱스인것은 temp에서 제거
			if (temp[0].second < left_point)
				temp.pop_front();

			else
				break;
		}

		while (temp.size() != 0)
		{
			//이제 들어오는 수 보다 크거나 같은 수들은 temp에서 제거
			//즉 이제 들어오는 수로 인해 앞으로 최솟값이 될 수 없는 수들 제거
			if (temp[temp.size() - 1].first >= a[right_point])
				temp.pop_back();

			else
				break;
		}
		temp.push_back(make_pair(a[right_point], i)); //이제 들어오는 수

		result.push_back(temp[0].first);
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";





	return 0;
}