[백준/Python] 1522 - 문자열 교환

문제

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

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

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

입력

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

출력

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

풀이
이 문제는 어떻게 해결해야하는지 감이 잘 안잡혔다
알고보니 내가 써본적없었던 슬라이딩 윈도우 개념이 필요해서 해결법이 떠오르지 않았던 것 같다
다행히 어렵지 않은 알고리즘이었고 새로운 알고리즘을 익히는 좋은 기회가 됐다

주어진 문장에서 a의 개수만큼 윈도우의 크기를 설정하고 문자열의 처음부터 한 칸씩 슬라이딩 하면서 윈도우 크기만큼 문자열을 슬라이싱했다
슬라이싱한 문자열 안의 b의 개수 만큼 교환이 일어나야하기 때문에 윈도우 내의 b의 개수를 기준으로 최소값을 찾아나갔다

코드

import sys

s = sys.stdin.readline().strip()

a_cnt = s.count("a")

s = s+s

min_ans = sys.maxsize
for i in range(len(s)-a_cnt):
    window = s[i:i+a_cnt]
    min_ans = min(min_ans, window.count("b"))
print(min_ans)

문제에서 원형 문자열이라는 조건을 제시했기 때문에 주어진 문자열을 그대로 한 번 더 이어붙였다