[PS] BOJ1522 문자열교환 ( SlidingWindow ) with JAVA

1522번: 문자열 교환

 

◎ 문제풀이

 

슬라이딩 윈도우 알고리즘을 알고 있으면 쉽게 풀리는 문제이다. ( 나는 모르고 있어서 해매었다.. ㄷ )

 

 

 

 

문제의 목적은 aaa 연속, bbb 연속으로 만드는 것이다. 

 

a의 개수는 3개이다. 

그럼 윈도우의 크기도 3이다. 

 

3의 크기로 하나씩 비교하며 a로 바꾸어야 하는 b의 개수의 최솟값을 구하면 된다. 

 

 

a로 바꾸어야 하는 b는 1개이다.

그럼 오른쪽으로 한칸 슬라이딩 해보자. 

 

 

a로 바꾸어야 하는 b는 1개이다.

그럼 오른쪽으로 슬라이딩 해보자. 

 

 

a로 바꾸어야 하는 b는 2개이다. 

 

이런 식으로 문자열 끝까지 한칸씩 슬라이딩하면 된다.

만약 윈도우가 문자열을 벗어나면 문자열은 원형이라고 했으므로 시작부분으로 돌아간다. 

 

 

a로 바꾸어야 하는 b의 최솟값은 1이므로 

정답은 1이다.

 

 

◎ 코드

import java.util.Scanner;

//BOJ1522 문자열교환
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int aCount = 0;
        int ans = Integer.MAX_VALUE;

        // 윈도우 크기 계산하기 : a의 개수 세기
        for(int i=0;i<str.length();i++ ){
            if(str.charAt(i)=='a'){
                aCount++;
            }
        }

        // 윈도우 안에 b의 개수 세기
        for(int i=0;i<str.length();i++){
            int end = i + aCount -1;
            int count = 0;
            for(int j=i;j<=end;j++){
                int pointer = j;
                if(j >= str.length()) pointer = j-str.length();
                if(str.charAt(pointer)=='b') count++;
            }

            // 윈도우 안의 b의 개수의 최솟값
            ans = Math.min(ans,count);
        }

        //출력
        System.out.println(ans);

    }
}