백준 | 문자열 교환

백준 문자열 교환

a, b의 위치에 관계 없이 원하는 문자열끼리 교환 가능하다.

모든 a가 연속이 되려면?

• 원형 문자열의 어떤 구간을 잘랐을 때, 그 구간에 속한 a의 개수가 처음 주어진 문자열의 a의 개수와 같아야 한다.
• 그렇지 않다면, 개수 차이만큼 b가 포함되어 있다는 말이므로, 그러한 b를 a와 교환해 주어야 한다.

따라서 처음 주어진 문자열의 a의 개수를 윈도우의 크기로 잡고, 슬라이딩 윈도우로 접근할 수 있다.

import sys

# 입력
s = sys.stdin.readline().rstrip()

# a_cnt: 문자열에 존재하는 a의 개수(윈도우의 크기)
a_cnt = s.count('a')

# b_cnt: 현재 윈도우의 b의 개수
b_cnt = s[:a_cnt].count('b')

# 원형 문자열이므로 s를 확장한다.
new_s = s + s[:-1]
min_b_cnt = b_cnt

# 슬라이딩 윈도우
for i in range(1, len(s)):
    # 다음 윈도우로 넘어가며, 양쪽 끝 문자를 확인한다.
    if new_s[i - 1] == 'b':
        b_cnt -= 1
    if new_s[i + a_cnt - 1] == 'b':
        b_cnt += 1
    
    min_b_cnt = min(min_b_cnt, b_cnt)

print(min_b_cnt)