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

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

스트레스 빡빡 받게 한 문제다.

이 문제를 풀면서, 큐 시스템에 적용을 할 수 있을 것 같다고 생각했다.

vip 관리와 우선순위가 있는 데이터들을 남겨둘 때 queue 구조(ex, redis, rabbitmq)에 적용할 수 있는 설계 기법 느낌이었다.

 

기가 막히고 코가 막힌다!

---

 

처음엔 map과 deque, mulitset과 deque, priority queue와 deque를 쓰면서 O(nlog(l))을 적용하면 아슬아슬하게 시간 제한을 맞출 수 있지 않을까 하는 생각에 조건문들을 건드려보았는데 되지 않았다.

 

결국은 O(N)이어야 한다는 것이다.

 

1. 현재 값보다 큰 값을 뒤에서부터 없애준다. ( 오름차순대로 위치할 수 있게 해준다.) - O(1)

2. deque에 index도 같이 저장하여 슬라이딩 윈도우 범위를 벗어난 값이 최솟값(front)에 있다면 삭제해준다. - O(1)

 

총 N*O(1) 연산이 보장되니 O(N)이다.

 

---

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <vector>
#include <string>
#include <map>
#include <limits.h>
#include <queue>
#include <set>
#include <math.h>
#include <stack>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, l;

	cin >> n >> l;

	deque<pair<int, int>> dq;

	int input;

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

		// input값보다 큰 앞에 값들 제거해주기
		while (!dq.empty() && dq.back().first > input) {
			dq.pop_back();
		}

		// 지워주고 뒤에 붙여주기
		dq.push_back(make_pair(input, i));

		// 인덱스 값이 슬라이딩 윈도우를 넘은 버릴 값일 때
		if (dq.front().second <= i - l) {
			dq.pop_front();
		}

		cout << dq.front().first << ' ';
	}

	return 0;
}