백준 11003 최솟값 찾기 [C++] 풀이 및 코드, 슬라이딩 윈도우, 쉬운 이해

문제

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

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

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>

using namespace std;

typedef pair<int, int> Node;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, l;
	cin >> n >> l;
	vector<int> arrInput(n, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> arrInput[i];
	}

	deque<Node> dq;

	
	for (int i = 0; i < n; i++)
	{
		int now = arrInput[i];
		//A번 
		while (dq.size() && dq.back().first > now)
		{
			dq.pop_back();
		}

		
		dq.push_back(Node(now, i));

		if (dq.front().second < i - l + 1)
		{
			dq.pop_front();
		}
		int res = dq.front().first;
		cout << res << " ";
	}
	return 0;
}

 

풀이

먼저 예제를 보자.

예제 입력 1 

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1 

1 1 1 2 2 2 2 2 3 3 2 2

 

쉽게 말하면, 입력된 정수 N개를 L개씩 묶었을 때, 최솟값을 찾는 문제이다.

여기서 어디부터~ 어디까지 묶는 범위를 알려줬는데, 이는 다음과 같다.

여기서 포함하는 범위가 0보다 작은 경우, 즉 음수인 경우는 포함하지 않는다고 하였다.

말만 어렵게 써놨지 결국, i번째 index를 하나씩 비교 하는 것은 동일하지만 비교군이 3개만 넘지 않으면 되는 문제다.

A번 코드 

이를 위하여 dequeue를 사용하는 방법이 있다.

- 일반 queue는 입구 출구가 각각 명확하여 FIFO 즉 먼저 들어온 노드가 먼저 나가는 구조를 가지고 있다

 

- dequeue는 입출구가 각각 양쪽에 있어서 양단에 있는 두 노드가 먼저 가가거나 들어올 수 있는 구조를 가지고 있다.

즉 push나 pop을 양단에서 할 수 있다는 의미다. 

 

편의상 dequeue를 dq로 부르겠다.

이 dq에 입력된 정수를 넣으면 dq는 다음과 같은 그림이 된다.

첫번째에는 index -2~0까지 비교를 하기 때문에, 비교할 대상이 0번 index 즉 1번밖에 없다.

따라서 front에 있는 노드를 출력하면 된다.

즉 최솟값이 front로 오는 원리로 진행하면 된다

 

그럼 두번째를 생각 해 보자. 두번째 범위 (-1~1)

비교를 했을 때, front에 있는 노드보다 5가 더 크다.

1 뒤에 back_push를 해두자.

이는 다음에 들어올 노드와 비교하기 위하여 push해놓아야 한다.

왜냐하면 다음 순번에서 1이 비교 범위에 없을 수 있고, 5가 최솟값이 되는 경우도 있기때문이다.

 

이제 최솟값을 찾는 원리를 보면 이전과 마찬가지로  최솟값이 front로 오는 원리와 동일하기에 front를 출력하면 된다.

 

그럼 3번째를 생각 해 보자.

 

마찬가지로 2를 back에 있는 노드와 비교하게 되는데 2가 더 작다.

이 경우는 5를 pop하여 1번 노드와 비교할 수 있도록 한다. ( 이는 dq를 사용하는 이유기도 하다. front에서 push를 하는 경우는 없지만, back에서는 push와 pop을 둘다 사용해야 한다.)

즉 dq에 2 , 4, 5, 6,가 있고, 1이 들어온 경우, 1이  가장 front에 있는 2와 비교될 수 있도록, 2, 4, 5, 6은 모두 1과 비교함과 동시에 pop해버림으로써 최솟값(front에 있는 노드)을 알 수 있는 것 이다.

또한 이는 비교 대상을 적게함으로써 시간을 단축시킬 수 있는 요소가 된다.

 

다음에 5를 pop하고 나면 1이 남게 되는데 1보다는 2가 더 크다.

따라서 1뒤에 back_push를 한다. (이유는 뒤에 설명함)

 

이제 3이 들어왔다고 생각하자(4번째).

마찬가지로 3은 2보다 크기 때문에, 2 뒤에 back_push를 하자.

3이 들어온 순간에서 비교 범위는, index 기준 1~3이다.

하지만 1은 index 0번이기 때문에 비교 범위가 아니게 된다.

 

따라서 front 노드의 index가 현재 비교 범위가 아닌 경우 pop을 해주어야 하기 때문에, index 정보를 노드가 알 고 있어야 한다.

pop을 해주고 난 뒤 4번째 비교에서는 다음과 같은 그림이 된다.

 

따라서 front에 있는 노드인 2가 최솟값이 된다.