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

문제

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

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

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

입력

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

출력

첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.

 

---

🌈 풀이 후기 

• 처음에는 어떻게 접근해야 할지 몰라서 투포인터를 고민하다가 다른 사람의 풀이를 보고 아이디어를 떠올렸다.
• a를 모두 연속으로 만들기 위해서 a의 길이를 먼저 구한 다음에 0부터 a의 길이만큼 확인해주면서 그안에 있는 b의 최소한의 교환으로 b만 옮겨주면 된다.

👩‍🏫 문제 풀이

양 끝이 연결되어 있으므로 % 문자열의 길이만큼 해줘야함. 

 

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

// a의 갯수를 구하고, 0부터 마지막까지 a의 길이만큼 돌면서 b의 교환 최소 횟수를 찾는다. 
// 양 끝이 연결되어있기 때문에 마지막 인덱스까지 길이만큼 % 해줘야함.
public class BOJ_G5_1522_문자열교환 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();

		int cnt = 0;
		int len = str.length();
		for (int i = 0; i < len; i++) {
			if (str.charAt(i) == 'a')
				cnt++;
		}

		int min = len;
		int bcnt = 0;
		for (int i = 0; i < len; i++) {
			bcnt = 0;
			// a의 길이만큼 + i범위 추가로 확인
			for (int j = i; j < cnt + i; j++) {
				if (str.charAt(j % len) == 'b')
					bcnt++;
			}
			min = Math.min(min, bcnt);
		}
		System.out.println(min);
	}

}