[백준] 1522: 문자열 교환 python 구현 / String

문제

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

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

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

 

풀이

1. a의 개수를 세고
2. a의 개수만큼 slicing한다
3. 슬라이싱한 외부와 바꿔가며 완전 a가 되기 위한 최소 개수를 확인한다.
4. 이후 슬라이딩 윈도우 방식으로 한 칸 씩 옮겨가며 최소개수를 비교한다.

 

CODE

import re
import copy

o_string = input()
# a의 개수를 세고
len_a = len(re.findall(r'a', o_string))
start = 0
min_exchange = 10e9
while 1:
    string = copy.deepcopy(o_string)

    # a의 개수만큼 슬라이싱
    end = start + len_a
    if end < len(string):
        space_a = list(string[start:end])
        space_b = list(string[:start] + string[end:])
    else:
        space_a = list(string[start:]+string[:end-len(string)])
        space_b = list(string[end-len(string): start])
    
    # 슬라이싱 외부와 바꿔가며 최소 개수를 확인
    exchange = 0
    for i, sa in enumerate(space_a):
        if sa == 'b':

            for j, sb in enumerate(space_b):
                if sb == "a":
                    space_a[i] = "a"
                    space_b[j] = "b"
                    break
            exchange += 1

    if exchange < min_exchange:
        min_exchange = exchange

    if start > (len(string)-1):
        print(min_exchange)
        break

    start += 1