[백준_1522번] 문자열 교환

[문제]

a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.

이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.

예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.

 

[입력 조건]

• 첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.

 

[코드]

import java.util.*;

public class BaekJoon_1522 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		int count=0; // a의 개수
		
		for(int i=0;i<str.length();i++) {
			if(str.charAt(i)=='a')
				count++;
		}
		
		// str의 문자열에서 a의 개수만큼 a가 연속적으로 나와야 함 
		int min=Integer.MAX_VALUE;
		for(int i=0;i<str.length();i++) {
			int b_move=0; // a 사이에 있는 b를 옮기기
			for(int j=i;j<i+count;j++) { 
				if(str.charAt(j%str.length())=='b') // 문자열은 원형 모양
					b_move++;
			}
			
			// a 사이에 있는 b의 이동 횟수가 가장 적은 경우 구하기
			min=Math.min(min, b_move);
		}
		System.out.println(min);
	}

}

 

[고찰]

 이번 문제의 핵심은 '문자열의 a의 개수만큼 a가 연속적으로 나와야함'이였다. 따라서 문자열에 포함된 a의 개수를 count 해준 후, 문자열의 start 지점 부터 start+count 길이까지 a의 개수가 연속적으로 나오나 검사해야 한다. 이때 그 사이에 있는 b를 이동시키면 되므로 모든 탐색 과정에서 a 사이에 있는 b의 개수가 적은 경우를 구해주면 된다.

 이번 문제 또한 슬라이딩 윈도우 문제였다. 이전 문제를 같은 유형을 풀어 구현은 어렵지 않았지만 해결 방법을 떠올리는 것이 어려웠다.