[BOJ/C++] 1522 문자열 교환

문제

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

풀이

문제 이해가 안돼서 문제 이해하려고 다른 사람 블로그 참고했는데 문제만 이해하면 쉬운 문제!

a가 연속적이어야 한다 🔄️ a가 a의 개수만큼 연속적으로 위치해야 한다

ex)
문자열 ababa
a 개수는 3개

인덱스 0 : ababa ➡️b가 1개 ➡️한 번의 교환 필요

인덱스 1 : ababa ➡️b가 2개 ➡️두 번의 교환 필요

인덱스 2 : ababa ➡️b가 1개 ➡️한 번의 교환 필요

인덱스 3 : ababa ➡️b가 1개 ➡️한 번의 교환 필요
(🌟문자열이 원형으로 이어져있으므로 끝까지 가서 끝나는 게 아니라, 다시 처음으로 가야함 => 다시 처음으로 돌아가도록 %로 index 구해야 함)

인덱스 4 : ababa ➡️b가 1개 ➡️한 번의 교환 필요

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

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

	int a_cnt = 0;
	string str;
	cin >> str;
	int ans = str.length();
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a')	a_cnt++;
	}

	for (int i = 0; i < str.length(); i++) {
		int b_cnt = 0;
		for (int j = i; j < i + a_cnt; j++) {
			int index = j % str.length();
			if (str[index] == 'b')	b_cnt++;
		}
		ans = min(ans, b_cnt);
	}

	cout << ans;

	return 0;
}