백준 1522

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

1522번: 문자열 교환

 

문제 이해

해당 문제의 경우 a가 연속으로 있기 위해선 몇개의 b를 교환해야 하는 가에 대한 문제이다.

해당 문제의 경우 모든 a가 연속으로 있으면 된다는 것을 기억하고 슬라이딩 윈도우 방식으로 풀었다.

https://soeasyalgo.tistory.com/49

슬라이딩 윈도우 알고리즘

슬라이딩 윈도우에 대해선 위에 설명을 참조하자

 

문제 풀이

a의 개수를 세고 a의 개수만큼을 슬라이딩 윈도우로 설정한다.

처음 부터 끝까지 윈도우에서 b가 얼마나 포함 되었는지 확인하고 

가장 적게 포함된 b의 개수를 출력한다.

import java.util.*;


public class test39 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        int min = Integer.MAX_VALUE;

        int aCnt = 0;
        //a의 크기를 계산 
        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i) =='a') {
                aCnt++;
            }
        }
        
        //b의 크기를 계산
        //해당 슬라이딩 윈도우에서 b가 존재 하면 해당 b만큼은 교환을 해줘야 a가 연속으로 있을 수 있다.
        for(int i=0; i<str.length(); i++) {
            int bCnt = 0;
            //처음 부터 끝까지 반복하는데 a의 크기만큼 반복
            for(int j=i; j<i+aCnt; j++) {
                //j가 범위를 넘어갈 수 있기에 나머지만큼만 계산
                int idx = j%str.length();
                //b만큼을 더함
                if(str.charAt(idx) =='b') {
                    bCnt++;
                }
            }
            //b가 가장 적게 나온 윈도우를 선택
            min = Math.min(min, bCnt);
        }
        System.out.println(min);
    }
}