문제

문제 바로가기

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

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

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

입력

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

출력

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

예제 입력

abababababababa

예제 출력

3

문제 검토

입력의 최대 길이가 1000밖에 되지 않는다.
완전 탐색을 떠올리면 좋다.

풀이(python)

Python

a=input()
acnt=a.count('a')
a+=a[0:acnt-1]
bmin=a[0:acnt].count('b')

for x in range(len(a)-(acnt-1)):
    if a[x:x+acnt].count('b')<bmin:
        bmin=a[x:x+acnt].count('b')
print(bmin)
    

한칸 씩 옮기며 a 크기만큼 문자열을 슬라이싱했고 그 중 b의 개수가 가장 적은 슬라이스의 b의 개수를 출력했다.

원형을 구현하기 위해서는 a크기만큼 슬라이싱 할 것이기 때문에 마지막 문자가 첫번째 문제가 됐을 때 슬라이스 될 수 있는 경우의 수까지 추가하기 위해서 a의 개수 - 1 만큼을 문자열 길이에 더 해줬다.

반복할 때는 마지막 문자가 첫번째 문자가 될 때가 마지막 반복이므로 반복 횟수에서는 a의 개수 - 1만큼을 빼주었다.

b의 개수가 가장 적은 a의 묶음에서 밖에 있는 a와 안에 있는 b를 하나씩 교환 하는 것이 최적의 해이므로 슬라이스 안에 b의 개수가 교환 횟수가 된다.

걸린 시간

37분 33초

총평

완전 탐색인 것은 떠올릴 수 있었지만, 일반 구현 문제와는 다르게 구현은 쉽고 알고리즘을 떠올리는 것이 어려웠다.