백준 1522 - 문자열 교환(Java)

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

1522번: 문자열 교환

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

abababababababa

예제 출력 1 복사

3

예제 입력 2 복사

ba

예제 출력 2 복사

0

예제 입력 3 복사

aaaabbbbba

예제 출력 3 복사

0

예제 입력 4 복사

abab

예제 출력 4 복사

1

예제 입력 5 복사

aabbaaabaaba

예제 출력 5 복사

2

예제 입력 6 복사

aaaa

예제 출력 6 복사

0

 

풀이

문제를 제대로 읽는데 오래걸렸던 문제,

0번째부터 문자열의 마지막까지 a의 갯수를 세고, 0부터 문자열의 마지막까지 탐색을 진행한다.

만약 b가 있다면 b를 카운트하고 b 카운트의 최솟값을 찾으면 된다.

주의할점은 문자열의 마지막을 처음과 붙여줘야 한다는 것이다.

해당 사항은 i+j가 문자열의 길이보다 클 때, 문자열의 길이만큼 빼줬다.

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

public class BJ_1522_문자열교환 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();
        int a_cnt = 0;
        int result = Integer.MAX_VALUE;
        for(int i=0; i<str.length(); i++)
        {
            if(str.charAt(i)=='a')
                a_cnt++;
        }
        for(int i=0; i<str.length();i++)
        {
            int b_cnt=0;
            for(int j=0; j<a_cnt;j++)
            {

                int index = i+j;

                if(index>=str.length()) {
                    index = i + j - str.length();
                }
                if(str.charAt(index)=='b') {
                    b_cnt++;
                }
            }
            result = Math.min(result,b_cnt);
        }
        System.out.println(result);
    }
}