[백준] 1522번: 문자열 교환 with Sliding Window

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

1522번: 문자열 교환

어렵게만 생각했는데 슬라이딩 윈도우를 잘 적용하면 문제가 훨씬 쉬워진다.

a와 b를 분리하는 것이므로 a의 개수를 센 뒤, 윈도우 크기를 설정한다.

그리고 윈도우를 한 칸씩 움직여보면서 해당 윈도우에 b의 개수를 최소인 경우를 찾아낸다.

#include <iostream>
#include <algorithm>
using namespace std;
int s, e;
int main(void) {
    string str;
    cin >> str;
    int len = str.length();
    int a_cnt = 0;
    
    for(int i = 0;i < len;i++) {
        if(str[i] == 'a') a_cnt++;
    }
    
    int min_cnt = len;
    for(int i = 0; i < len;i++) {
        int cnt = 0;
        for(int j = 0;j < a_cnt;j++) {
            if(str[(i + j) % len] == 'b') cnt++;
        }
        min_cnt = min(min_cnt, cnt);
    }
    
    cout << min_cnt << '\n';
}