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

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

[CS Academy] Word Ordering

問題

https://csacademy.com/contest/beta-round-1/task/word_ordering/statement/

文字列の並び替えに関する問題です。与えられた辞書式順列で並び替えを行います。

考え方

Comparatorを定義して優先順位を決めます。

Mapのキーに文字を値に優先順位を格納します。大文字は小文字よりも優先順位が低いので、小文字は [ 0 , 25]、大文字は  [26 - 51] の値を取ることになります。この値を元にComparatorを定義します。

コード

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class WorldOrdering {
    static Map<Character, Integer> map = new HashMap<Character, Integer>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        int N = scan.nextInt();
        String[]w = new String[N];
        for(int i = 0; i < N; i++) {
            w[i] = scan.next();
        }
        scan.close();
        for(int i = 0; i < 26; i++) {
            char c = s.charAt(i);
            char C = (char)(c - 'a' + 'A');
            map.put(c, i);
            map.put(C, 26 + i);
        }
        Arrays.sort(w, new MyComparator());
        for(String t : w) {
            System.out.println(t);
        }

    }
    static class MyComparator implements Comparator<String>{
        @Override
        public int compare(String s0, String s1) {
            int l = Math.min(s0.length(), s1.length());
            if(s0.substring(0, l).equals(s1.substring(0, l))) {
                if(s0.length() == s1.length()) {
                    return 0;
                }else if(s0.length() > s1.length()) {
                    return 1;
                }else {
                    return -1;
                }
            }else {
                for(int i = 0; i < l; i++) {
                    char c0 = s0.charAt(i);
                    char c1 = s1.charAt(i);
                    if(c0 == c1) continue;
                    if(map.get(c0) > map.get(c1)) {
                        return 1;
                    }else {
                        return -1;
                    }
                }
                if(s0.length() == 0) {
                    return 1;
                }else {
                    return -1;
                }
            }
        }
    }
}