문제 풀이

투포인터 또는 슬라이딩 윈도우를 활용하면 풀 수 있다.

먼저 a의 개수를 세어주고 a개수만큼 인덱스 0부터 시작해서 0 ~ a의 개수의 구간에 b가 몇개인지 세어준다.

그러면 0 ~ a의 구간에서는 방금 세어준 b개를 교환을 해야지 a가 연속되게 배치될 수 있다.

그렇다면 이 구간을 한칸씩 움직이면서 구간안에 b의 개수가 최소가 되는 값을 찾으면 된다.

이 문제에서는 문자열의 시작부분과 끝부분이 이어져있기 때문에 끝부분이 문자열의 길이를 넘기면 문자열의 길이만큼 빼줘서 문자열의 시작부분과 이어지게 만들어주면 된다.

문제 링크

boj/1522

소스코드

PS/1522.java

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int [] arr = new int[1001];
	public static void main(String[] args) throws IOException {
		String s = br.readLine();
		int a_cnt = 0;
		for(int i=0;i<s.length();i++)
		{
			if(s.charAt(i)=='a')
				a_cnt++;
		}
		int b_cnt=0;
		for(int i=0;i<a_cnt;i++)
		{
			if(s.charAt(i) == 'b')
				b_cnt++;
		}
		int ans = b_cnt;
		for(int i=1;i<s.length();i++)
		{
			if(s.charAt(i-1)=='b')
			{
				b_cnt--;
			}
			int r =i+a_cnt-1;
			if(r >=s.length())
			{
				r-=s.length();
			}
			if(s.charAt(r) == 'b')
				b_cnt++;
			ans = Math.min(ans, b_cnt);
		}
		System.out.println(ans);
	}

}