[백준] 1522: 문자열 교환 - JAVA

23 Sep 2023 in Algorithm on 브루트포스 알고리즘

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

풀이

a와 b로 이루어진 문자열이 주어지고, a를 모두 연속으로 만들어야 한다.

원형 문자열이기 때문에 aaabbba와 같은 문자열도 연속이다.

a의 개수를 세어 aCount에 저장했다.

문자열을 처음부터 끝까지 탐색하면서

해당 인덱스를 시작으로하고 길이가 aCount인 부분문자열에서 b의 개수를 세주고 ans를 최솟값으로 갱신했다.

b의 개수만큼 바꾸면 a가 연속이게 된다.

---

메모리: 14268KB

시간: 128ms

언어: Java 11

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int aCount = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == 'a') {
                aCount++;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < str.length; i++) {
            int bCount = 0;
            for (int j = i; j < i + aCount; j++) {
                if (str[j % str.length] == 'b') {
                    bCount++;
                }
            }

            ans = Math.min(ans, bCount);
        }

        System.out.println(ans);
    }

}