BOJ11003 최솟값 찾기

www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

i-L+1 ~ i 번 째 수 중 최솟값 출력

 

덱 이용하기

• 내 앞의 수가 나보다 크다 ⇒ 그 수는 필요없다.
• 내 앞의 수가 나보다 작다 ⇒ 내가 나중에 필요할 수도 있다.

 

push는 뒤에서만 해준다.

덱을 앞에서부터 볼 때 읽은 순으로, 값은 오름차순으로 정렬되도록 한다.

1. 범위를 벗어난 값은 pop front

2. 앞의 수 중 나보다 큰 것 pop back
  * 이때 앞의 수의 범위는 확인할 필요 없음. (이미 전 단계에서 pop했음) ⇒ 시간 초과

3. pop이 모두 끝나면 push back

4. front가 현재 범위 내의 최솟값

 

 

 

코드

//finding minimum
#include <cstdio>
#include <queue>
using namespace std;

deque<pair<int, int>> M;
int main() {
	int N, L, tmp;
	scanf("%d%d", &N, &L);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &tmp);
		while (!M.empty() && M.front().second <= i - L) M.pop_front();
		while (!M.empty() && M.back().first >= tmp) M.pop_back();
		M.push_back({ tmp,i });

		printf("%d ", M.front().first);
	}
	return 0;
}

 

 

아니 덱이래서 덱으로 푸는데 자꾸 시간초과가 나는 거

그래서 PQ로도 풀어봤는데 당연히,, 어림도 없지

알고보니 겁나 비효율적으로 짜놓았음

push를 뒤에서만 해주면 된다는 걸 깨달으면 간단한 듯.