11003번 (platinum 5)

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

 문제를 읽어보면 알겠지만, 최솟값을 구하기 위해서 슬라이딩 윈도우 알고리즘을 사용하는게 적절한 문제이다.

 

 그러나 주어진 숫자의 개수가 꽤나 큰 숫자이므로, nlogn의 시간복잡도를 가지는 정렬을 사용하면 시간초과가 생기기 때문에, n의 시간복잡도를 가지는 특별한 유사 정렬방법을 생각해낼 필요가 있다.

 

#include <iostream>
#include <deque>

using namespace std;
typedef pair<int, int> Node;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, L;
	cin >> N >> L;
	int start = 2 - L, end = 1;
	deque<Node> win;
	int tmp;

	for (int i = 1; i <= N; ++i) {
		cin >> tmp;

		while (win.size() && win.back().second >= tmp) {	// deque의 크기가 0이 아니고, deque의 끝 부분의 content값이 입력받은 수보다 클 때 
			win.pop_back();
		}

		win.emplace_back(Node(i, tmp)); // deque의 크기가 0 이거나, deque의 끝 부분의 content값이 입력받은 수보다 작다.

		if (win.front().first < start) //첫번째 원소의 인덱스 값이 start 인덱스 값보다 작으면
			win.pop_front();

		cout << win.front().second << " ";


		end++; start++;
	}

	return 0;
}

 

 입력받는 값이 적었다면, 그냥 단순 nlogn정렬을 사용해도 상관없었겠지만 값이 많기 때문에, 특별한 정렬 효과를 볼 수 있는 방법을 사용해야한다. 해당 문제를 푸는데 deque 자료구조를 사용해보았는데, 예제 입력을 살펴보면

12 3

1 5 2 3 6 2 3 7 3 5 2 6이고, i <= Ai는 무시하기 때문에, 첫번째 window범위는

 

start = 2-L = -1 , end = 1

(index = 1, value =1)

 첫번째 deque는 이런 상태가 될 것이고, 가장 첫번째 원소가 가장 작기 때문에 value 1값을 출력하고, 계속해서 window의 start값과 end값이 커질 것이기 때문에, 두번째 deque에선

 

start = 3-L = 0, end = 2

(index = 1, value =1)

(2, 5)

가 되는데 여기서 집어넣기 전에 deque.back().second 즉, 넣기전 마지막 deque의 value값과 현재 삽입할 value값을 비교해서 삽입할 value가 더 작다면 deque.pop_back()으로 값을 제거하고 계속해서 새로운 deque의 마지막 값과 비교해가면서 deque의 마지막 값이 더 작아질 때 까지 값을 제거해가고, deque의 마지막 값이 더 작다면 그때 새로운 value값을 삽입한다. 그리고 value값 1을 출력한다.

 

여기서는 deque의 마지막 value값이 1이고 삽입할 값이 5기 때문에 마지막 값을 pop하지 않고, 그대로 (2, 5)를 집어넣는다.

 

그 다음 세번째 deque에선

 

start = 4-L = 1, end = 3

 

(index = 1, value =1)

(3, 2)

가 되는데, 그 전에 마지막 deque.back().second값 즉 5가 새로 삽입할 값인 2보다 크기 때문에, (2,5)를 pop하고 그 다음 deque의 마지막 요소와 비교해간다. 그렇게 위의 결과가 이루어지고, 가장 좌측의 값을 출력하면 최솟값을 찾는 것인데, 여기서 window가 계속해서 이동하므로, 출력하기전에 가장 좌측의 값의 index값이 start보다 작은지 비교해보고 작다면 deque.pop_front()하여 첫번쨰 요소를 제거하고 출력한다.