[BOJ] 11003번_최솟값 찾기_덱

[문제]

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

N개의 수 A1,A2,...,AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최소값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하는 문제이다. 이때, i <= 0인 Ai는 무시하고 D를 구해야한다.

*이 문제는 인터넷의 도움을 받아 해결했다. 역시 플래티넘 난이도의 문제는 어려운 것 같다...

[사용 알고리즘]

덱, 슬라이딩 윈도우

[풀이 핵심]

• Ai-L+1 ~ Ai의 수 중 최소값이 될 수 있는 수를 덱에 담아 슬라이딩 윈도우를 사용하는 식으로 해결하는 문제이다.
• 덱은 pair을 사용하여 value와 index를 저장한다. (deque<pair<값, 인덱스>> d)
• 덱은 항상 오름차순 정렬되어있기 때문에 덱의 front의 index가 Ai-L+1미만(범위 밖)이면 pop해준다.
• 덱이 항상 오름차순인 이유는 v[i]의 값이 덱의 back의 value보다 작을경우 v[i]의 값이 더 커질 때까지 pop하기 때문이다. 예를 들어 설명하면 덱에 12456이 존재하고 v[i]가 3일때, 456은 더 이상 최소값이 될 수 없기 때문에 전부 pop해주고 3를 push해줘서 덱의 원소는 123이 되는것이다.

[코드]

//boj11003번_최솟값 찾기_덱

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, L;
	cin >> N >> L;

	vector<int> v;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	deque<pair<int, int>> d;

	vector<int> result;

	for (int i = 0; i < N; i++) {
		if (!d.empty() && d.front().second < i - L + 1) {
			d.pop_front();
		}

		while (!d.empty() && d.back().first > v[i]) {
			d.pop_back();
		}

		d.push_back({ v[i],i });
		result.push_back(d.front().first);
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}