[백준] 1522 - 슬라이딩 윈도우

a가 연속적이여야 한다는 말은 a가 a의 개수 만큼 연속적으로 위치해야 한다는 뜻이다.

예를 들어, "ababa" 라는 문자열이 있다면, a가 3개이므로 "aaabb", "baaab", "bbaaa".... 등 a가 3개 연속적으로 위치해야한다.

 

따라서, 인덱스 0 부터 끝까지 a의 개수 만큼의 길이를 슬라이딩 윈도우로 생각하고 b의 개수를 세면 b를 교환하면 된다.

예를 들어, "ababa" 라는 문자열이 있다고 하자. 이때 a의 개수는 3개이다.

인덱스 0 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 1 : ababa -> b가 2개 -> 두 번의 교환 필요
인덱스 2 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 3 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 4 : ababa -> b가 1개 -> 한 번의 교환 필요

 

 

import sys

x=sys.stdin.readline().rstrip()

numA=x.count('a')
#print(numA)

listNum=[]
#print(listNum)

for k in range(len(x)):
    stringNew=x[k:numA+k]
    n=len(stringNew)
    numBefore=0
    if(len(stringNew)<numA):
      stringBefore=x[0:numA-n]
    #  print(stringBefore)
      numBefore=stringBefore.count('b')
    #print(stringNew)
    numB=stringNew.count('b')
    listNum.append(numB+numBefore)
    #print(listNum)
    

#print(listNum)
print(min(listNum))