[BOJ_1522] 문자열 교환

슬라이딩 윈도우 기법을 오랜만에 적용 해보아서 처음에 꽤나 헤맸던 문제다.

 

aaabbaa 라는 문자열이 있으면 a의 갯수만큼 카운팅해서 그때의 존재하는 b의 갯수를 세면 총 옮겨야 하는 교환의 횟수가 된다.

 

ababababab -> 중 a가 5개다. 즉, a 5개가 연속되면 된다. 그럼 여기서 ababa의 경우를 보면 b 두개 빼고 그 위치에 a 나머지 두개를 넣는다고 생각하면 된다.

 

이런식으로 생각을 하면 떠오르기가 쉬운데 처음에 캐치하기 힘들었던것 같다.

 

그리고, 문제 조건 중 원통의 구조로 마지막과 처음이 이어진 circle_queue 처럼 생각을 해야 하는 부분이 있다.

 

슬라이딩 윈도우가 처음이라면 블로그에 정리하였으니 찾아보면 좋을 것 같다. 

슬라이딩 윈도우

 

아래는 슬라이딩 윈도우 기법을 사용해서 푼 풀이이다.

package Sliding_Window;
import java.util.*;
import java.io.*;
public class BOJ_1522 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        String str = tk.nextToken();
        int acnt = 0;
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == 'a'){
                acnt++;
            }
        }
        int windowSum = 0;
        for(int i = 0; i < acnt; i++){

            if(str.charAt(i) == 'b') {
                windowSum++;
            }
        }
        int sum = Integer.MAX_VALUE;
        for(int i = acnt; i < str.length(); i++){
            if(str.charAt(i-acnt) == 'b'){
                windowSum--;
            }
            if(str.charAt(i) == 'b') {
                windowSum++;
            }
            sum = Math.min(sum,windowSum);
        }
        for(int i = str.length(); i < str.length() + acnt; i++){
            int before = (i-acnt)%str.length();
            if(str.charAt(before) == 'b'){
                windowSum--;
            }
            int after = i%str.length();
            if(str.charAt(after) == 'b') {
                windowSum++;
            }
            sum = Math.min(sum,windowSum);
        }
        System.out.println(sum);
    }
}

 

 

1522번: 문자열 교환