문자열 교환 - 백준 #1522, 브루트포스 알고리즘/슬라이딩 윈도우

문제

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

출력

첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

예제

입력	출력
abababababababa	3
ba	0
aaaabbbbba	0
abab	1
aabbaaabaaba	2
aaaa	0

풀이

string = input()
a_cnt = string.count('a')    # a의 개수
string += string[0:a_cnt-1]    # 원형 처리
min_val = 1001

for i in range(len(string)-(a_cnt-1)):
    # 윈도우 내부의 b와 외부의 a 교환하면 a 모두 연속
    min_val = min(min_val, string[i:i+a_cnt].count('b'))
print(min_val)