백준 1522번 : 문자열 교환 (자바)

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

 

문제

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

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

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

---

입력

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

---

출력

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

 

🔵 풀이

문제를 이해하는데에 어려움을 겪었습니다. 예제 1번인 ababababababa의 경우 세번째 a와 두번째 b를 교환하게 되면 aaabbabababa가 됩니다. 이후 네번째 a와 세번째를 b를 교환하면 aaaabbbababa가 됩니다. 마지막으로 다섯번째 a와 다섯번째 b를 바꾸면 aaaabbbbbaaa가 되므로 3번의 교환으로 a가 연속되는 문자열을 만들 수 있습니다. (문자열은 원형으로 처음과 끝이 이어져 있습니다.) 이 문제는 결국 모든 a를 연결하는것으로 a의 총 개수를 세어주었습니다. 그리고 슬라이딩 크기를 a의 총 개수만큼 설정한 후 그 안에 있는  b의 개수를 세어 최솟값을 찾아주었습니다.

 

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

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String ab = br.readLine();
    int bCount = 0;
    int aCount = 0;
    int min = Integer.MAX_VALUE;

    for (int i=0; i<ab.length(); i++){
      if (ab.charAt(i)=='a'){
        aCount++;
      }
    }

    for (int i=0; i<ab.length(); i++){
      for (int j=i; j<i+aCount; j++){
        int tmp = j;
        if (tmp>=ab.length()){
          tmp%=ab.length();
        }
        if (ab.charAt(tmp)=='b')bCount++;
      }
      min = Math.min(min,bCount);
      bCount=0;
    }

    System.out.println(min);
  }
}