[코딩테스트] [BOJ11003] 최솟값 찾기

문제

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

---

풀이

1. 숫자를 기록할 int형 벡터, index를 기록할 덱을 선언한다.

2. n번만큼 반복문을 돌며 숫자를 입력받고, 덱이 비어있거나 조건을 통과하면 push_back 해준다.
   2-1. 현재 인덱스 - 탐색할 범위 값이 덱의 front보다 작거나 같은 경우, 덱에 들어있는 인덱스가 현재 인덱스 범위에 더이상 포함하지 않다는 뜻이기에 pop_front 해준다.
   => 해당 단계를 수행하고 나면 덱에는 front부터 오름차순으로 현재 범위 인덱스가 삽입되어 있다.
   2-3. 덱의 back을 인덱스로 하는 요소가 현재 인덱스 요소보다 크거나 같다면 pop_back 해준다.
   2-4. 현재 인덱스를 덱에 push_back 해준다.

3. 덱의 front가 탐색한 구간 중 최솟값을 보장하기 때문에, 출력해준다.

+) 입/출력 속도까지 계산해주어야 백준 기준 통과 가능

---

코드

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
using namespace std;

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

	int n = 0, l = 0;
	cin >> n >> l;

	vector<int> field(n, INT_MAX);
	deque<int> indexs;
	for (int i = 0; i < n; i++)
	{
		cin >> field[i];

		while (!indexs.empty() && indexs.front() <= i - l)
		{
			indexs.pop_front();
		}

		while (!indexs.empty() && field[indexs.back()] >= field[i])
		{
			indexs.pop_back();
		}

		indexs.push_back(i);

		cout << field[indexs.front()] << " ";
	}

	return 0;
}