백준11003 최솟값 찾기

작성일 | In

문제 링크

  • http://icpc.me/11003

사용 알고리즘

  • Sliding Window
  • Deque

시간복잡도

  • O(N)

풀이

작년 8월에 세그먼트 트리로 풀다가 TLE가 나온 문제입니다.

아래 코드와 같이 deque를 이용해 구간의 최솟값을 관리해주면 됩니다.
최악의 경우에도 N개의 원소에 대해 각각 1번의 삽입과 1번의 제거 연산을 하기 때문에 O(N)으로 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
deque<p> dq;

int main(){
	int n, m; cin >> n >> m;
	for(int i=0; i<n; i++){
		int t; cin >> t;
		while(dq.size() && dq.front().y <= i-m) dq.pop_front();
		while(dq.size() && dq.back().x >= t) dq.pop_back();
		dq.push_back({t, i});
		cout << dq.front().x << " ";
	}
}