백준 1522

●문제 출처

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

●정리(요약)
a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

●코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		char[] arr = str.toCharArray();
		
		// 1) 전체 a 개수
		 int k = 0;
	     for (int i = 0; i < arr.length; i++) {
	         if (arr[i] == 'a') {
	        	 k++;
	         }
	     }
	     
	    // a가 0개거나 전부 a면 바꿀 필요 없음
	    if (k == 0 || k == arr.length) {
	        System.out.println(0);
	        return;
	    }
	    
	    int bCnt = 0;
        for (int i = 0; i < k; i++) {
            if (arr[i] == 'b') {
            	bCnt++;
            }
        }
		
        int ans = bCnt;
        
        // 슬라이딩 윈도우
        for (int start = 1; start < arr.length; start++) {
            // 윈도우에서 빠지는 문자
            if (arr[start-1] == 'b') {
            	bCnt--;
            }

            // 윈도우에 새로 들어오는 문자 (원형)
            int end = (start + k - 1) % arr.length;
            if (arr[end] == 'b') {
            	bCnt++;
            }

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

        System.out.println(ans);
	}
}

●느낀 점
1차 시도에는 처음과 끝은 서로 인접해있어서 뒤에서부터 'a' 갯수를 세고
처음부터 뒤에서의 'a' 갯수를 빼고 정렬된 배열과 비교 후 다른 횟수를 세어 2를 나눴다...

정답은 a갯수 만큼 슬라이딩 윈도우로 끝까지 세어 최소로 구하는 것을 만들었다!