백준 - 1522번 : 문자열 교환(C++)

풀이 방법 : 슬라이딩 윈도우

문제에서 문자열이 원형으로 이루어져 있다고 했기 때문에 a를 연속으로 만드는 방법은 a를 가운데로 몰아넣거나 b를 가운데로 몰아넣는 경우 두 가지가 있을 수 있다.

a를 가운데로 몰아넣는 경우에는 a의 갯수를 세서 그 크기만큼의 슬라이딩 윈도우를 움직여가면서 그 구간 안에 존재하는 b의 갯수를 최소로 만들어주면 된다.
b를 가운데로 몰아넣는 경우는 그 반대로 시행하면 된다.

#include <iostream>

using namespace std;

int main()
{
	string Str;
	cin >> Str;

	int N = Str.length();

	int BWindowSize = 0;
	int AWindowSize = 0;

	for (int i = 0; i < N; ++i)
	{
		if (Str[i] == 'b')
			++BWindowSize;

		else
			++AWindowSize;
	}

	// b를 가운데로 몰아넣는 경우
	int ACnt = 0;

	for (int i = 0; i < BWindowSize; ++i)
	{
		if (Str[i] == 'a')
			++ACnt;
	}

	int Min = ACnt;

	for (int i = 0; i < N - BWindowSize; ++i)
	{
		if (Str[i] == 'a')
			--ACnt;

		if (Str[i + BWindowSize] == 'a')
			++ACnt;

		Min = min(Min, ACnt);
	}
    
	//a를 가운데로 몰아넣는 경우
    
	int BCnt = 0;

    
	for (int i = 0; i < AWindowSize; ++i)
	{
		if (Str[i] == 'b')
			++BCnt;
	}

	int MinA = BCnt;

	for (int i = 0; i < N - AWindowSize; ++i)
	{
		if (Str[i] == 'b')
			--BCnt;

		if (Str[i + AWindowSize] == 'b')
			++BCnt;

		MinA = min(MinA, BCnt);
	}

	Min = min(MinA, Min);

	cout << Min;
}