Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-24SRM340, SRM341, SRM342 (Practice)

SRM 342 TagalogDictionary

|  SRM 342 TagalogDictionary - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 342 TagalogDictionary - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7411

  • やるだけ。
    • Comparatorの中に変数を仕込む方法が分からなかったので仕方なくバブルソートでやった
import java.util.Arrays;
import java.util.Comparator;

public class TagalogDictionary {

	int[] ord;
	int ngord;
	
	public int compare(String arg0, String arg1) {
		if (arg0.equals(arg1)) {
			return 0;
		}
		int al = arg0.length();
		int bl = arg1.length();
		int aidx = 0;
		int bidx = 0;
		while (aidx < al && bidx < bl) {
			char a = arg0.charAt(aidx);
			char b = arg1.charAt(bidx);
			int aval = ord[a];
			int bval = ord[b];
			aidx++;
			bidx++;
			if (a == 'n' && aidx < al) {
				if (arg0.charAt(aidx) == 'g') {
					aval = ngord;
					aidx++;
				}
			}
			if (b == 'n' && bidx < bl) {
				if (arg1.charAt(bidx) == 'g') {
					bval = ngord;
					bidx++;
				}
			}
			if (aval < bval) {
				return -1;
			} else if (aval > bval) {
				return 1;
			}
		}
		if (aidx >= al) {
			return -1;
		}
		return 1;
	}
	
	public String[] sortWords(String[] words) {
		String order = "a b k d e g h i l m n ng o p r s t u w y";
		
		
		String[] cp = order.split(" ");
		int cl = cp.length;
		ord = new int[512];
		ngord = 0;
		for (int i = 0 ; i < cl ; i++) {
			if (cp[i].length() == 1) {
				ord[cp[i].charAt(0)] = i;
			} else {
				ngord = i;
			}
		}
		
		int len = words.length;
		for (int y = 0 ; y < len ; y++) {
			for (int x = 0 ; x < len - 1 ; x++) {
				int i = x;
				int j = x + 1;
				String a = words[i];
				String b = words[j];
				int comp = compare(a, b);
				if (comp > 0) {
					String t = words[i];
					words[i] = words[j];
					words[j] = t;
				}
			}
		}
		
		return words;
	}
}