[백준] 1522 문자열 교환 / 구현 / python 실1

슬라이딩 윈도우 풍년이네

https://www.acmicpc.net/problem/1522

a랑 b 섞인 문자열이있고

 

문자 위치를 교환해서 a가 쭉 연속된 문자열로 만들기 위해

필요한 최소 교환 횟수를 구해야 한다

 

문자열이 원형이라 처음과 끝이 이어져있다는게 관건

 

원형 처리를 원활하게 하기 위해 문자열을 두번 이어붙인다

 

처음 size만큼의 문자에서 b의 개수를 세어 초기 윈도우 값으로 사용한다

 

1부터 문자열 길이번째 원소까지 탐색한다

슬라이딩하면서 윈도우의 왼쪽 문자를 제거하고, 오른쪽 문자를 추가하면서

한 칸씩 이동한다

이때 왼쪽 문자가 b였으면 b개수-1, 오른쪽 문자가 b였으면 b개수+1한다

 

이전 최소 값과 현재 값을 min으로 비교해서 업데이트한다

 

계속 윈도우를 이동시키면서 b의 개수가 최소로 포함되는 구간을 찾는 방법을 사용한다

 

s = input()

# a의 개수를 구함
size = s.count('a')
# 원형을 고려해 문자열을 두 번 이어붙임
s_extended = s + s

# 초기 윈도우에서 b의 개수를 세기
current_b_count = 0
for i in range(size):
    if s_extended[i] == 'b':
        current_b_count += 1

# 최소 b의 개수를 초기값으로 설정
min_b_count = current_b_count

# 슬라이딩 윈도우
for i in range(1, len(s)):
    # 윈도우의 맨 왼쪽 문자 제거
    if s_extended[i - 1] == 'b':
        current_b_count -= 1
    # 윈도우의 오른쪽 끝 문자 추가
    if s_extended[i + size - 1] == 'b':
        current_b_count += 1
    # 최소값 갱신
    min_b_count = min(min_b_count, current_b_count)

print(min_b_count)