[백준] 1522 문자열 교환 [java]

문제

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

투 포인터 슬라이딩 윈도우

start와 end 지점을 설정해 놓고, start++ / ++end를 진행하며 옆으로 이동하는 알고리즘이다.
배열이나 리스트에서 한 칸씩 이동하면서 어떤 조건을 확인할 때, 사용하면 좋다.
한 칸 이동할 때마다 해당 범위를 모두 탐색하며 조건을 확인하면 시간복잡도가 O(n^2)이지만,
슬라이딩 윈도우를 사용하면 O(n)으로 줄어든다.

문제 풀이

모든 a가 연속되게 배치해야 한다.
따라서, a의 갯수만큼 범위를 설정하고, 해당 범위 안에 b가 제일 적을 때의 b의 갯수를 구하면 된다.

abababababababa 이 예제에서, a의 갯수는 8개이다. 8개를 연속되게 놓으면 된다.
1. (abababab)abababa
-> 이렇게 하면 괄호 안에 b가 4개 이므로, 괄호 안의 b 4개와 괄호 밖의 a 4개를 교환하면 되므로 4번 교환이 일어난다.
2. a(babababa)bababa
-> 이번에도 괄호 안에 b가 4개 이므로, 괄호 안의 b 4개와 괄호 밖의 a 4개를 교환하면 되므로 4번 교환이 일어난다.
3. abababa)bababab(a
-> 괄호 안에 b가 세개이므로, 괄호 안의 b 3개와 괄호 밖의 a 3개를 교환하면 되므로 3번 교환이 일어난다.

코드

import java.util.Scanner;

// 슬라이딩 윈도우
public class Boj1522 {
//public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();

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

        int start = 0, bCnt = 0, end = aSize - 1;
        for(int i = 0; i < aSize; i++){
            if(str.charAt(i) == 'b') bCnt++;
        }

        int min = bCnt;
        while(start < str.length()){
            if(str.charAt(++end % str.length()) == 'b') bCnt++;
            if(str.charAt(start++) == 'b') bCnt--;

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

        System.out.println(min);
    }
}