山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.559 swapAB列

文字列に関する問題

No.559 swapAB列 - yukicoder

レベル1.5の問題も残り5問となりました。今回は文字列に関する問題を取り上げます。

AとBからなる文字列Sが与えられます。この文字列SをAAA…ABB…Bとなるように並び替えます。 並び替えは隣同士の文字を入れ替えることしかできません。このとき、文字列を並び替える時に、文字の入れ替え回数の最小値を求めよということです。

考え方

並び変え終わった後の文字列において、AとBの境界はSに含まれるAの個数となります。ここで、Aの個数を a とします。境界の値は a - 1となります。また、文字列の長さを l とします。

Sの0から a - 1番目までに含まれるBの数が入れ替えられるべき文字となります。最小となる入れ替え方法は自信がないんですが、 a - 1 から  0 に向かってSを調べ、Bとなっている番地 i l - 1 から a に向かってAとなっている番地 jを入れ替えます。このとき入れ替え回数は j - i となります。これを並び替えが終わるまで繰り返します。

他の人の解説を見るともっと簡単なようでした。あれま。

コード

import java.util.Scanner;

public class Exec0559 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        scan.close();
        int l = S.length();
        int cnt1 = 0;
        //int cnt2 = 0;
        for(int i = 0; i < l; i++) {
            char c = S.charAt(i);
            if(c == 'A') {
                cnt1 ++;
            }
        }
        //cnt2 = l - cnt1;
        if(l == 1) {
            System.out.println(0);
            System.exit(0);
        }
        int k = l - 1;
        int sum = 0;
        for(int i = cnt1 - 1; i >= 0; i--) {
            char c = S.charAt(i);
            if(c == 'B') {
                for(int j = k; j >= cnt1 - 1; j --) {
                    char c2 = S.charAt(j);
                    if(c2 == 'A') {
                        k = j - 1;
                        sum += j - i;
                        break;
                    }
                }
            }
        }
        System.out.println(sum);
    }
}