백준 1522 문자열 교환 Python

🐸 문제 정보

1522번: 문자열 교환

 

🤖 알고리즘

슬라이딩 윈도우

 

⏱️ 풀이 시간

30m+

 

📝 풀이

교환이라는 단어의 뜻이 명확하게 서술되어있지 않아서 한 번 이상하게 풀었다가 다시 풀었다.

이 문제에서 말하는 교환은, 단어 안에서 각 글자간 위치를 변경하는 경우를 말한다. (질문 게시판에 나와 같은 사람이 꽤 있었다...)

우선 문제는 슬라이딩 윈도우로 풀면 그렇게 어렵지 않다.

 

1. 입력받은 문자열에서 a의 개수를 센다
2. 문자열에서 a개씩 슬라이딩 윈도우하며, 해당 위치에 b의 개수의 최소값을 구한다
   • 생각해보면 a의 개수는 정해져있기 때문에, 해당 길이 만큼에 존재하는 b의 개수가 곧 위치를 교환해야하는 b의 개수이기 때문이다.
   • 중요한 것은, 이 문제는 원형이기 때문에 끝점과 시작점이 이어져있다는 것이다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

word = list(input().rstrip())
n = len(word)
a = word.count('a')
res = sys.maxsize

for i in range(n):
    if n < i + a:
        temp = word[i:] + word[:(i + a) % n]
    else:
        temp = word[i:i + a]
    res = min(res, temp.count('b'))

print(res)