[C++] 슬라이딩 윈도우

슬라이딩 윈도우

• 범위를 지정하고, 범위를 유지한 채로 이동하며 문제를 해결한다.
• 투 포인터 알고리즘과 비슷하다.
• 슬라이딩 윈도우의 크기(탐색 범위)는 일정하다.

 

관련 문제들

• 백준 12891 (실버2)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int s, p;
	cin >> s >> p;	//dna문자열의 길이 s, 비밀번호로 사용할 부분 문자열의 길이 p

	string dnaString;
	cin >> dnaString;

	char ACGT[4] = { 'A','C','G','T' };
	int ACGTNum['Z'] = {};	// A,C,G,T 각각의 최소 개수
	for (int i = 0; i < 4; i++)
	{
		cin >> ACGTNum[ACGT[i]];
	}

	int newACGTNum['Z'] = {};
	for (int i = 0; i < p; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			if (dnaString[i] == ACGT[j])
				newACGTNum[ACGT[j]]++;
		}
	}

	int answer = 0;
	int start_index = 0;
	int end_index = start_index + p - 1;
	while (end_index < s)
	{
		bool flag = false;
		for (int i = 0; i < 4; i++)
		{
			if (ACGTNum[ACGT[i]] > newACGTNum[ACGT[i]])
			{
				flag = true;
				break;
			}
		}
		if (!flag)
		{
			answer++;
		}
		start_index++;
		end_index++;
		
		// 새 배열 업데이트
		if (end_index < s)
		{
			newACGTNum[dnaString[start_index - 1]]--;
			newACGTNum[dnaString[end_index]]++;
		}
		else 
			break;
	}
	cout << answer << '\n';

	return 0;
}

• 백준 11003 (플레티넘5)

// 시간 복잡도를 고려하지 않고 막 풀었을 때
#include <iostream>
#include <algorithm>
using namespace std;

long long A[5000001] = {};

int minIndexFunc(const int& L, const int start_index)
{
	unsigned int min = 0xffffffff;
	int minIndex = -1;
	for (int i = start_index; i < start_index + L; i++)
	{
		if (min > A[i])
		{
			min = A[i];
			minIndex = i;
		}
	}
	return minIndex;
}

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

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

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

	int min_index = 0;
	
	// 첫번째
	cout << A[min_index] << ' ';	

	// ~L번째
	for (int i = 0; i < L - 1; i++)
	{
		if (A[min_index] > A[i + 1])
			min_index = i + 1;
		cout << A[min_index] << ' ';
	}

	// L~N번째
	int start_index = 1;
	int end_index = start_index + L - 1;
	while (end_index < N)
	{
		if (start_index - 1 == min_index)
		{
			// 새 범위 내 최솟값 구하기
			min_index = minIndexFunc(L, start_index);
		}
		if (A[end_index] < A[min_index] || A[end_index] == A[min_index])
		{
			min_index = end_index;
		}

		cout << A[min_index] << ' ';
		start_index++;
		end_index++;
	}

	return 0;
}

// 시간 복잡도를 인지하고 적절한 자료구조 deque를 사용함.
// O(nlogn)이 걸리는 정렬 알고리즘을 사용하지 않고도 슬라이딩 윈도우와 덱을 이용해 정렬 효과를 봄.
#include <iostream>
#include <deque>
using namespace std;

typedef pair<int, int> Node;

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

	deque<Node> dequeArray;

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

	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;

		while (!dequeArray.empty() && dequeArray.back().second > a)
		{
			dequeArray.pop_back();
		}

		dequeArray.push_back({ i,a });

		if (dequeArray.front().first + L <= i)
		{
			dequeArray.pop_front();
		}

		cout << dequeArray.front().second << ' ';
	}

	return 0;
}