문제 ✨
1522번: 문자열 교환
a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.
이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.
예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.
첫번째 풀이
s = input()
a_cnt = s.count('a')
b_cnt = len(s)
total = len(s)
for i in range(total):
if a_cnt <= total-i:
cnt = s[i:i+a_cnt].count('b')
else:
cnt = s[i:].count('b') + s[:a_cnt-(total-i)].count('b')
if b_cnt > cnt: b_cnt = cnt
print(b_cnt)두번째 풀이
s = input()
a_cnt = s.count('a')
b_cnt = len(s)
s2 = s*2
for i in range(len(s2)):
if i+a_cnt > len(s2)-1: break
else:
cnt = s2[i:i+a_cnt].count('b')
if b_cnt > cnt: b_cnt = cnt
print(b_cnt)원형 문자열 처리: 슬라이딩 윈도우
a의 총 개수만큼 슬라이싱한 구간에서 b의 개수
나머지 구간에서의 a와 슬라이싱된 구간의 b 교환
b -> a 교환이 최소로 이루어지는 구간을 찾는 방식
