[백준] #1522 문자열 교환(python)

📌문제

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

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

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

입력

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

출력

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

예제 입력1

abababababababa

예제 출력1

3

예제 입력2

ba

예제 출력2

0

예제 입력3

aaaabbbbba

예제 출력3

0

예제 입력4

abab

예제 출력4

1

예제 입력5

aabbaaabaaba

예제 출력5

2

예제 입력6

aaaa

예제 출력6

0

백준 1522번 문제

💡Idea

슬라이딩 윈도우 기법을 사용하여 해결한 문제입니다.

슬라이딩 윈도우 구현 자체는 쉽지만, 슬라이딩 윈도우를 생각해내기가 굉장히 어려웠던 문제입니다🥴

🙋‍♀️ : 그럼 슬라이딩 윈도우로 어떻게 이 문제를 해결할 수 있을까요?!

우선 입력받은 문자열의 총 a 개수가 슬라이딩 윈도우의 사이즈가 됩니다.

a가 연속되기 위해서는 슬라이딩 윈도우 안에 있는 문자들이 모두 a가 되어야 합니다.
즉, 슬라이딩 윈도우 안의 b들을 모두 슬라이딩 윈도우 밖의 a와 교환하면 됩니다.

우리는 필요한 교환의 최소 횟수를 찾아야 하기 때문에, 슬라이딩 윈도우를 계속해서 이동해가면서 슬라이딩 윈도우 내 b의 개수의 최솟값을 찾아주면 됩니다.

💻코드1

• ⏰ 시간 : 68 ms / 메모리 : 30840 KB

import sys
alpha_str = sys.stdin.readline().strip() # 입력받은 문자열
window_size = len([alpha for alpha in alpha_str if alpha == 'a']) # 슬라이딩 윈도우 사이즈 : a의 개수
ans = len(alpha_str) - window_size # b의 개수
for i in range(len(alpha_str)): # i는 윈도우의 시작 인덱스
    count = 0 # 윈도우 내의 b의 개수
    for j in range(window_size): # 윈도우 시작 지점부터 윈도우 사이즈만큼 확인
        current = (i + j) % len(alpha_str) # 원형 문자열 구현
        if alpha_str[current] == 'b': count += 1
    ans = ans if ans < count else count
print(ans)

📝코드 설명

해당 문자열은 원형 문자열로 생각하기 때문에, 문자열의 끝에 도달하면 문자열의 맨 처음으로 가주어야 합니다.

따라서, 아래와 같은 식을 통해 인덱스가 문자열의 길이 이상이 되면 문자열의 맨 앞에서부터 다시 차례차례 확인할 수 있도록 해줍니다.

$I$ : 계산된 인덱스
$L$ : 문자열의 길이
$Circular Index = I \;mod \;L$

💻코드2

첫번째 for문을 아래와 같이 count를 사용하여 해결할 수도 있습니다.

for i in range(len(alpha_str)): # i는 윈도우의 시작 인덱스
    last_index = (i + window_size) % len(alpha_str) # 윈도우의 마지막 인덱스
    count = alpha_str[i:last_index].count('b') if i <= last_index \
        else (alpha_str[i:]+alpha_str[:last_index]).count('b')
    ans = ans if ans < count else count

1. i <= last_index인 경우
   

이 경우, 그냥 i부터 last_index까지의 부분 리스트 중 b의 개수를 찾아주면 됩니다.

단, 문자열에 a가 하나도 없는 경우 window_size는 0이 되는데, 이 경우 i와 last_index가 같은 값이 될 수 있으므로 =도 빼먹지 말아야 합니다!

2. i > last_index인 경우
   

이 경우, i부터 문자열의 끝까지, 그리고 문자열의 처음부터 last_index까지의 범위 중에서 b의 개수를 찾아주어야 합니다.

따라서, alpha_str[i:]+alpha_str[:last_index]의 범위 내에서 count를 진행합니다.

💻코드3

import sys

alpha_str = sys.stdin.readline().strip()
window_size = alpha_str.count('a')
ans = len(alpha_str) - window_size

for i in range(0, len(alpha_str) - window_size + 1): # 코드 2의 1번 경우
    ans = min(ans, alpha_str[i:i+window_size].count('b'))

for i in range(0, window_size - 1): # 코드 2의 2번 경우
    ans = min(ans, (alpha_str[:i+1]+alpha_str[i-window_size+1:]).count('b'))
    
print(ans)

코드2번에서 두 가지 경우를 if문으로 구분하여 b의 개수를 각각 세어주었다면, 위 코드처럼 처음부터 두 경우를 각각 for문 두 개로 구현하여 문제를 해결할 수도 있습니다.