파이썬) 문자열 교환 - BOJ

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

 

s = input()  # 문자열 입력
a = s.count('a')  # 입력된 str에서의 a의 개수

answer = float('inf')


s = s + s[0:a-1]


for i in range(len(s) - (a-1)):

    answer = min(answer, s[i:i+a].count('b'))

print(answer)

 

문제는 연속된 b를 만들기 위해 몇 번의 교환을 해야할까?를 묻는 문제다.

바꿔말하면 문자열 s중 0번 부터 a의 개수만큼까지는 a로 가득 채워져있어야한다는 뜻이다. 이를 잘 기억해서 다음과 같이 풀어보자.

문자열이

abababababababa

라고 생각해보자.

a의 개수는 8이다.

즉 aaaaaaaabbbbbbb가 되어야 연속된 b를 만들 수 있다.

(abababab)abababa 괄호를 친 만큼은 a로 연속되어야 있어야하니, 저 괄호 안에 있는 b는 괄호 밖에 있는 a와 교환되어야한다.

하지만 인덱스 0번부터 7번까지만 확인하면 최소 교환수를 알 수가 없다. 그러므로 반복문으로 i부터 i+8만큼 슬라이싱하여 b의 개수를 확인해야한다.

(abababab)abababa
a(babababa)bababa
ab(abababab)ababa
.
.
.

 

주의할 점은 이 문자열 s는 원형이기에 끝과 끝이 이어져있다는 것이다.

즉, 우리는 s의 마지막에서 s의 0번부터 a-1만큼 s에 더해주어야한다.

이를 잘 생각하며 코드를 짜면 문제없이 풀어낼 수 있다.