문자열 교환 ( 1522 번 )

1522번: 문자열 교환

 

---

🧠 알고리즘

• 슬라이딩 윈도우(Sliding Window)

 

✔️ 동작 방식

• 윈도우 크기는 a_count가 됨.
• 원형 문자열이므로, 문자열을 2배로 확장(new_str = n_str * 2).
• 윈도우 안의 b 개수는 "해당 구간에서 a로 채워야 하는 교환 횟수"를 의미한다.
• 모든 구간을 확인한 후, 최소 교환 횟수를 결과로 반환한다.

---

 

🧾 코드

import sys

def _main(n_str):
    answer = float('inf')
    a_count = n_str.count('a')
    new_str = n_str * 2

    for idx in range(len(n_str)):
        window = new_str[idx:idx + a_count]
        answer = min(answer, window.count('b'))
    
    return answer


n_str = sys.stdin.readline().rstrip()
print(_main(n_str))

---

 

⏱️ 시간 복잡도

for idx in range(len(n_str)) : 문자열 길이 만큼 순회 ( 선형 시간 복잡도 )
	answer = min(answer, window.count('b')) : 원도우 사이즈에서 'b' 찾기 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )