BOJ 1522 - 문자열 교환

문제

a와 b로만 이루어진 원형 문자열에서 인접한 문자끼리 교환하여 모든 a를 연속으로 모으기 위한 최소 교환 횟수를 구하라.

입력

a와 b로 이루어진 문자열이 주어진다.

출력

최소 교환 횟수를 출력한다.

예제

입력	출력
`aabbba`	`1`

풀이

a의 총 개수를 윈도우 크기로 설정하고, 원형 문자열에서 슬라이딩 윈도우로 윈도우 내 a의 최대 개수를 구한다.

a의 총 개수 tot를 구하고, 윈도우 크기를 tot로 설정한다
문자열을 두 번 이어붙여 원형을 처리한다
윈도우를 한 칸씩 슬라이딩하며 윈도우 내 a의 개수를 추적한다
tot - (윈도우 내 최대 a 개수) = 최소 교환 횟수

핵심 아이디어: a를 tot 크기의 연속 구간에 모아야 하므로, 이미 a가 가장 많이 포함된 윈도우를 찾으면 나머지만 교환하면 된다.

코드

def min_a(word):
    tot = word.count("a")
    ac = word + word
    cur = ac[:tot].count("a")
    max_a = cur
    for i in range(1, len(word)):
        if ac[i - 1] == "a":
            cur -= 1
        if ac[tot + i - 1] == "a":
            cur += 1
        max_a = max(max_a, cur)
    return tot - max_a
 
 
print(min_a(input()))

복잡도

시간: O(N)
공간: O(N)

문제