[백준] 1522번 문자열 교환 (파이썬)

 

문제

 

1522번: 문자열 교환

 

 

 

 

정답 소스코드 (Python)

 

arr=input()
result=[]
size=arr.count('a')     #윈도우 크기

for i in range(len(arr)):
    b_count=0
    for j in range(size):
        index=i+j
        if index>len(arr)-1:index-=len(arr)     #index가 리스트를 넘어간다면 -=리스트크기 해주기-> 원형 유지
        if arr[index]=="b":b_count+=1
    result.append(b_count)

print(min(result))

 

 

풀이  (Python)

 

 

문자열 교환은 많은 알고리즘에서 다루는 문제로 필수적으로 짚고 넘어가야 할 문제이다. 문자열 교환 문제는 a를 모두 연속적으로 만들 돼 최소 교환 횟수를 출력해야 하며, 맨 처음과 끝은 이어져있다고 판단한다.

 

 

Point 1)  슬라이딩 윈도우 

 슬라이딩 알고리즘은 10개의 리스트에서 5개의 원소로 연속된 부분집합을 확인할 때 총 5번의 부분집합을 확인하게 되는데, 부분집합이 순서대로 있는 경우, 다음 부분집합은 전 부분집합의 첫 원소가 없어지고 새로운 원소만 들어온 후 나머지의 3개는 동일한 원소이기에 3개의 원소의 중복 계산을 막기 위함이다. 

 

이 문제에 적용하면, 전체에서 a와 b를 교환하는 전부의 경우의 수를 검사하는 것이 아닌, 윈도우를 정해놓고 그 안에서 최댓값 또는 최소 값을 찾는 방식이다. a를 모두 이어지게 하는 것이기 때문에, 윈도우의 사이즈는 a의 개수가 된다.

 

 

aabbaaabaaba

 

 

위의 예시로 설명하면, a의 개수는 8개로 윈도우의 사이즈는 8이 된다.

첫 원소부터 8개를 보면 [ a, a, b, b, a, a, a, b]가 된다. 이때 a를 모두 연속적으로 만들기 위해서는 b 3개를 a 3개와 교환해야 하므로 교환 횟수는 3이다. 즉 교환횟수는 해당 윈도우에서 b의 개수를 의미한다.

 

이와 같이 윈도우 시작점을 for문을 통해 1칸씩 늘려나가면, 결과는 아래와 같다.

1. [ a, a, b, b, a, a, a, b] => 교환 횟수: 3

2. [ a, b, b, a, a, a, b, a] => 교환 횟수: 3

3. [ b, b, a, a, a, b, a, a] => 교환 횟수: 3

4. [ b, a, a, a, b, a, a, b] => 교환 횟수: 3

5. [ a, a, a, b, a, a, b, a] => 교환 횟수: 2

6. [ a, a, b, a, a, b, a, a] => 교환 횟수: 2

7. [ a, b, a, a, b, a, a, a] => 교환 횟수: 2

8. [ b, a, a, b, a, a, a, b] => 교환 횟수: 3

 

∴ 최소 교환 횟수는 2이다. 

 

 

 

Point 2)  원형 구조 

 

문제의 조건 중 문자열의 처음과 끝은 이어져 있다는 조건이 있으므로 윈도우 체크 for문 안에  간단한 if문 처리로 해결할 수 있다.

 

#index가 리스트를 넘어간다면 -=리스트크기 해주기-> 원형 유지
if index>len(arr)-1:index-=len(arr)