C++ 백준 11003 최솟값 찾기

백준 11003

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

11003번: 최솟값 찾기

 

풀이 전 나의 생각

N개의 수와 L이 주어질 때, D의 조건을 만족하며 저장된 수를 출력해야 한다.

 

조건

- 1 ≤ L ≤ N ≤ 5,000,000

- 109 ≤ Ai ≤ 109

 

과정

N의 범위를 보면 절대로 단순 2중 for문으로는 풀 수 없다는 것을 알 수 있다.

 

따라서 이를 해결하기 위해 우선순위 큐와 덱과 같은 자료구조를 사용해야 하는데
이 풀이에선 덱을 사용하여 진행했다.

 

먼저 D의 조건을 보자.
i - L + 1 ~ i의 범위 중 최솟값을 탐색한다고 나와있다.

그럼 L이 3이라 가정하고 i를 1부터 차례대로 넣어보면 

 

-1 ~ 1, 0 ~ 2, 1 ~ 3, 2 ~ 4, 3 ~ 5....

i <= 0은 무시하고 D를 보면
L만큼 구간별로 탐색하는 것을 확인할 수 있다. ( 1 ~ 3, 2 ~ 4, 3 ~ 5 )

다음으로 덱을 이용하여 최솟값을 찾아야 한다.

이를 위해서는 조건이 2가지 필요하다.

1. 덱에 존재하는 자료의 수가 L의 탐색 범위를 넘어서면 안된다.
2. 덱 맨 앞의 자료를 최솟값으로 설정하기 위해 현재 비교하는 수보다 큰 덱의 자료는 모두 삭제한다.

먼저 2번을 예로
덱의 자료가 3, 5, 8이 있다고 가정하자. 
다음에 들어오는 자료가 4일 때, 최소를 구하기 위해 5, 8의 후보군이 필요하지 않을 것이다.
왜냐하면 4보다 큰 값은 절대 최솟값이 될 수 없기 때문이다.

 

따라서 자료 4가 들어올 때는 덱의 자료는 3, 4가 되며 항상 맨 앞에 있는 값을 최솟값으로 만들어준다.
결론은 덱의 맨 앞의 자료는 항상 최소여야 하기 때문에 불필요한 최솟값 후보들을 모두 삭제해준다.

1번을 예로 
이전에 D는 L의 수만큼 구간을 탐색하는 것을 알아냈다.
그러므로 현재 탐색 순번 i = L + 맨 앞 최솟값의 위치
라면 L의 탐색 구간을 벗어났다는 소리기 때문에
맨 앞의 덱의 자료를 삭제해준다.

추가 설명으로 맨 앞의 최솟값이 무난하게 L의 구간을 벗어날 정도로 존재했다면
없애주는 것이다. 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	//덱의 자료와 위치를 저장
	deque<pair<int, int>> dq;
	vector<int> N_vec(N + 1);

	for (int i = 1; i <= N; i++)
	{
		cin >> N_vec[i];
	}

	for (int i = 1; i <= N; i++)
	{
		//L의 구간 탐색 범위를 벗어난다면 앞의 자료 삭제
		if (!dq.empty() && i == dq.front().second + L) dq.pop_front();

		//현재 자료보다 큰 자료들이 있을 경우 모두 삭제 (덱 맨 앞에 최솟값을 두기 위해)
		while (!dq.empty() && dq.back().first > N_vec[i]) dq.pop_back();
		
		//자료와 위치 저장 (구간을 벗어나는지 알기 위해 위치 저장)
		dq.push_back({ N_vec[i], i });
		cout << dq.front().first << " ";
	}
}