[백준 1522] 문자열 교환

[백준 1522] 문자열 교환

문제 링크

#include <iostream>
#include <algorithm>
using namespace std;
string str;

void solve(){
    int n = str.length();
    int cnt = 0;
    for(int i=0; i<n; i++){
        if(str[i] == 'a'){
            cnt++;
        }
    }

    if(cnt == 0) {
        cout << 0 << endl;
        return;
    }

    int ans = 987654321;
    for(int i=0; i<n; i++){
        int temp_cnt = 0;
        for(int j=i; j<i + cnt; j++){
            if(str[j % n] == 'b'){
                temp_cnt++;
            }
        }
        ans = min(ans, temp_cnt);
    }

    cout << ans << endl;
}

int main() {

    cin >> str;
    solve();

    return 0;
}

• 모든 b를 a로 만드는줄 알았는데, 그게 아니라 모든 a를 인접하게 만드는 것이다.
• 맨 처음, 모든 a의 갯수를 센다.
• a의 갯수가 0이라면 모든 a가 인접해있으므로 0을 리턴한다.
• 문자열의 길이만큼 돌면서, a의 갯수만큼 윈도우를 정하고, b의 갯수를 센다.
• 한 칸씩 윈도우를 옮긴다. 단, 환형이기 때문에 모듈화 연산을 해줘야 한다.
• 이 때 b의 갯수의 최솟값이 답이다.
• b의 갯수의 최솟값이라는 의미가 교환 해야할 b의 갯수가 제일 적다는 뜻이기 때문이다.