문제 접근

문제를 읽어보고 처음엔 어렵게 느껴졌다. 하지만, N의 크기(문자열 길이)와 시간복잡도(2초)를 보고 N^2에도 풀릴 것이라 생각했고, 이때부터 사고가 좀 유연하게 그냥 브루트 포스로 접근하자고 생각하니 쉽게 풀렸다.

결국 a문자열은 쭉 이어져야 한다. 그렇다면 a문자의 갯수가 X개라면,

• a문자가 0번인덱스~X-1번 인덱스까지 쭉 이어진 경우
• a문자가 1번인덱스~X번 인덱스까지 쭉 이어진 경우
• a문자가 2번인덱스~X+1번 인덱스까지 쭉 이어진 경우
  ...
• a문자가 X-1번인덱스~X-2번 인덱스까지 쭉 이어진 경우

를 모두 생각해보면 된다. 결국은 정해진 a구간 내에 있는 모든 b를 제거해서 외부로 내쫓아야 한다. 즉, 각 구간 안에서 b의 갯수를 구하고, 그 중 최솟값을 답으로 제시하면 된다.

문제 풀이

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

public class Main {
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        N = s.length();

        int aSize = 0;
        for (int i = 0; i < N; i++) {
            if (s.charAt(i) == 'a') aSize++;
        }

        int min = N;
        for (int i = 0; i < N; i++) {
            int bCount = 0;
            int moveCount = 0;
            while (moveCount != aSize) {
                if (s.charAt((i + moveCount) % N) == 'b') {
                    bCount++;
                }
                moveCount++;
            }
            min = Math.min(min, bCount);
        }
        System.out.println(min);
    }
}