백준 1522 문자열 교환

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

문제의 핵심은 결국
a를 하나로 뭉쳐놓게 만드는 것이 포인트이다.

그렇다면 어떤 부분을 정해서 b를 교환했을때 최소로 a를 일렬로 나열할 수 있을지 생각해보아야 한다.

문자열의 길이가 1000밖에 되지 않기 때문에,
0번부터 a의 갯수 만큼 슬라이딩 윈도우를 통해 b의 개수가 최소인 구간을 찾아주면 된다.

1) 파이썬 코드

k = input()
a_cnt = k.count('a')
ans = 1001
for i in range(len(k)):
    sub = ''
    if i + a_cnt >= len(k):
        comp = (i + a_cnt) % len(k)
        sub = k[i:len(k)] + k[0:comp]
    else:
        sub = k[i:i+a_cnt]
    b_cnt = sub.count('b')
    ans = min(ans,b_cnt)
print(ans)

2) 자바 코드

import java.io.*;
import java.util.*;

public class Main {
    private static String x;
    private static int ans = 1001;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        x = br.readLine();
        int a_cnt = 0;
        for (int i = 0; i < x.length(); i++) {
            if (x.charAt(i) == 'a') {
                a_cnt += 1;
            }
        }

        for (int i = 0; i < x.length(); i++) {
            int b_cnt = 0;
            for (int j = i; j < i+a_cnt; j++) {
                int idx = j % x.length();
                if (x.charAt(idx) == 'b') {
                    b_cnt += 1;
                }
            }
            ans = Math.min(ans, b_cnt);
        }
        System.out.println(ans);
    }

}