[백준] 1522번 문자열 교환 (자바 풀이)

문제

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

1522번: 문자열 교환

 

풀이

이 문제는 아이디어가 매우 중요하다. 알고리즘 분류에 슬라이딩 윈도우로 표시되어 있는 것을 보고 힌트를 얻었다.

 

a가 연속적이여야 한다는 말은 a가 a의 개수 만큼 연속적으로 위치해야 한다는 뜻이다.

예를 들어, "ababa" 라는 문자열이 있다면, a가 3개이므로 "aaabb", "baaab", "bbaaa".... 등 a가 3개 연속적으로 위치해야한다.

 

따라서, 인덱스 0 부터 끝까지 a의 개수 만큼의 길이를 슬라이딩 윈도우로 생각하고 b의 개수를 세면 b를 교환하면 된다.

예를 들어, "ababa" 라는 문자열이 있다고 하자. 이때 a의 개수는 3개이다.

 

인덱스 0 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 1 : ababa -> b가 2개 -> 두 번의 교환 필요
인덱스 2 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 3 : ababa -> b가 1개 -> 한 번의 교환 필요
인덱스 4 : ababa -> b가 1개 -> 한 번의 교환 필요

 

따라서 b를 최소한으로 교환하는 것이 정답이므로 한 번의 교환만 있으면 a를 연속적으로 만들 수 있다.

 

 

코드

import java.util.*;


public class Baekjoon_1522 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		
		int min = Integer.MAX_VALUE;
		
		int aCnt = 0;
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i) =='a') {
				aCnt++;
			}
		}
		
		for(int i=0; i<str.length(); i++) {
			int bCnt = 0;
			for(int j=i; j<i+aCnt; j++) {
				int idx = j%str.length();
				if(str.charAt(idx) =='b') {
					bCnt++;
				}
			}
			min = Math.min(min, bCnt);
		}
		
		System.out.println(min);
	}
}