[Java] 백준 1522번: 문자열 교환

[문제 바로 가기] - 문자열 교환

💡 일단 생각하기!

어제는 투 포인터, 오늘은 슬라이딩 윈도우 문제다.

먼저 a를 모두 연속으로 만들기 위해서 a의 개수를 센다.
a의 개수만큼의 슬라이딩 윈도우를 만든 후 그 안에 b가 몇개 있는지 센다.
즉, b의 개수 = 교환 횟수가 되므로 b의 개수 중 최소값을 구해주면 된다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 1522번 문자열 교환
 * - 슬라이딩 윈도우 사용해서 a 개수만큼의 범위에서 b의 개수를 세서 최소값 구하기
 * 
 * 메모라 : kb 시간 : ms
 */
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split("");
		
		int aCnt = 0; // a 개수
		for (int i = 0; i < str.length; i++) {
			if (str[i].equals("a")) aCnt++;
		}
		
		int start = 0; // 슬라이딩 윈도우 시작 인덱스
		int end = aCnt - 1; // 슬라이딩 윈도우의 끝 인덱스
		int bCnt = 0; // b 개수
		for (int i = 0; i < aCnt; i++) {
			if (str[i].equals("b")) bCnt++;
		}
		
		int min = bCnt;
		while (start < str.length) {
			// 문자열은 원형이므로 (end % str.length)
			if (str[++end % str.length].equals("b")) bCnt++;
			if (str[start++].equals("b")) bCnt--;
			
			min = Math.min(min, bCnt);
		}
		
		System.out.println(min);		
	}
}