白準1213ファリンdromの作成(実装)

3641 ワード
ジャワ アルゴリズム#アルゴリズム# テキストリンク
これは解決するのに長い時間がかかる問題です.2週間前からほぼ3~4回挑戦しましたが、実施力不足のためか、かなり時間がかかりました.
まず考える方法は正しい.
指定された文字列の長さが偶数の場合、偶数文字が必要です.例えば、AABBCDの場合、Aは2個、Bは2個、Cは1個、Dは1個なのでダメです.対称なので奇数個ではありません.
指定された文字列の長さが奇数の場合、奇数の文字は1文字のみ許可されます.例えば、ABCABの場合、Aは2個、Bは2個、Cは1個であるため、パリン症候群を作成することができる.しかし、ABCACCであれば不可能です.
また,重要な部分は,複数の正解があれば辞書順に前の回答を出力することである.例えば、ABAABAがあれば、答えはAABBAAであるべきです.そのため、前の文字を先に処理する必要があります.この言葉は次のコードと同じです.
for(int i=0; i<alpha.length; i++){      //사전 순으로 앞서려면 아스키 코드가 빠른 순서부터 우선적으로 처리
                for(int j=0; j<alpha[i]/2; j++){
                    output += (char)(i + 'A');
                }
            }
すべてのコード
import java.util.*;

public class Main {
    static String output = "";
    static String s;
    static String add_String(String k){
        String n = "";
        for(int i=k.length()-1; i>=0; i--){
            n += k.charAt(i);
        }
        return n;
    }

    public static void main (String[]args){
        Scanner scanner = new Scanner(System.in);
        s = scanner.next();  //홀수개 글자면 하나만 홀수 나머지 짝수.. 짝수개 글자면 모든게 짝수..
        int[] alpha = new int[26];

        for(int i=0; i<s.length(); i++){
            alpha[s.charAt(i) - 'A']++;
        }
        int center = 0;
        int cnt = 0;
        for(int i=0; i<alpha.length; i++){
            if(alpha[i] % 2 != 0){
                cnt++;
                center = i;
            }
        }
        if(cnt >= 2 || (s.length() % 2 == 0 && cnt >= 1))
            System.out.print("I'm Sorry Hansoo");
        else {
            for(int i=0; i<alpha.length; i++){      //사전 순으로 앞서려면 아스키 코드가 빠른 순서부터 우선적으로 처리
                for(int j=0; j<alpha[i]/2; j++){
                    output += (char)(i + 'A');
                }
            }
            if(s.length() % 2 != 0){
                String k = output;
                output += (char)(center + 'A') + add_String(k);
                System.out.print(output);
            }
            else {
                System.out.print(output + add_String(output));
            }

        }
    }
}
奇数文字であれば、真ん中の字を付けて逆さにします.
Pythonアルゴリズム-90(プログラマー)カーペット
[Algorithm]Baekjun中間-最大臀部、最小臀部探索バイナリ