[ BOJ ] 1522 : 문자열 교환 ( SILVER 1 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/1522)

문제

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

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

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

입력

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

출력

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

풀이 과정

a를 모두 연속으로 만들기 위해선, b도 연속으로 만들어야 a도 연속이다. (aaabbb, baaaab, bbbbaab)

즉 b를 전부 붙여야 하므로, b의 전체 갯수만큼의 슬라이딩 윈도우를 만들어 특정 위치에 b를 전부 옮길 때 필요한 교환 횟수의 최솟값을 출력한다.

 

예를 들어, aababab 라는 문자열이 있다면 전체 b의 갯수는 3개이므로 3 크기의 슬라이딩 윈도우를 만든다.

(aab)abab -> b 2개를 교환해야 함. (2)

a(aba)bab -> b 2개를 교환해야 함. (2)

aa(bab)ab -> b 1개를 교환해야 함. (1)

aab(aba)b -> b 2개를 교환해야 함. (2)

aaba(bab) -> b 1개를 교환해야 함. (1)

a)abab(ab -> b 2개를 교환해야 함. (2)

aa)baba(b -> b 2개를 교환해야 함. (2)

 

풀 때는 이렇게 생각했는데, 사실 그냥 a 를 연속으로 만들기 위해 a의 전체 갯수만큼 슬라이딩 윈도우를 만들어 b 자리에 a를 옮겨도 될 것 같다. ㅠ

 

import sys
input = sys.stdin.readline

string = input().rstrip()
b = string.count('b')
result = string[:b].count('a')

for i in range(1, len(string)):
    if i + b <= len(string):
        result = min(result, string[i:i+b].count('a'))
    else:
        result = min(result, string[i:].count('a') + string[:i+b-len(string)].count('a'))

print(result)