[yukicoder] No.559 swapAB列

文字列に関する問題

No.559 swapAB列 - yukicoder

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

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

考え方

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

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

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

コード

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);
    }
}