BOJ 11003 최솟값 찾기

기본 풀이가 deque 인 것 같은데

priority queue 두개로 푼게 기-묘 해서 올려봅니다

 

<풀이>

1. i 로 순회를 한다고 할 때 0 <= i < L 까지는 priority queue에 push하며 가장 작은 값을 top으로 출력한다.

  ㄴ 아래 소스코드의 priority_queue<int> pq 의 top이 현재 구간의 최솟값

2. L <= i < N 이 됐을 때, i - L 인덱스의 값 ( arr[i - L] ) 을 pq에서 제거 해야 한다.

3. priority queue의 특성 상 pop 밖에 할 수 없기 때문에 해당 값이 없을 경우 삭제 예약을 한다

  ㄴ 아래 소스코드의 priority_queue<int> reserved 에 넣는 것으로 삭제 예약

4. 지워야 할 reserved의 값이 pq의 top보다 작다면 어차피 구간의 최소값에 영향을 미치지 않음

5. pq의 top과 reserved의 top이 같을 때 같이 pop

  ㄴ pq의 top이 현재 구간의 최솟값으로 유지됨

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <numeric>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#define re return
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)

#define DEBUG true

typedef pair<int, int> pii;
typedef long long ll;

int arr[5000000];
int main() {
	ios::sync_with_stdio( false );
	cin.tie( 0 ); cout.tie( 0 );

	int N, L; cin >> N >> L;
	
	priority_queue<int> pq;
	priority_queue<int> reserved;
	for ( int i = 0; i < N; i++ ) {
		cin >> arr[i];
		pq.push( -arr[i] );

		if ( pq.size() > L ) {
			reserved.push( -arr[i - L] );
		}
		
		while ( !reserved.empty() ) {
			if ( pq.top() == reserved.top() ) {
				pq.pop();
				reserved.pop();
			}
			else {
				break;
			}
		}
		cout << -pq.top() << ' ';
	}

	return 0;
}