Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-15SRM374 (Practice)

SRM 374 SyllableSorting

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

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

  • 問題文の通りに実装する。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SyllableSorting {

	public class S implements Comparable<S> {
		List<String> slist;
		List<String> ulist;
		String base;
		S (List<String> l, String b) {
			ulist = new ArrayList<String>();
			slist = new ArrayList<String>();
			for (String a : l) {
				ulist.add(a);
				slist.add(a);
			}
			Collections.sort(slist, new Comparator<String>(){
				public int compare(String a, String b) {
					int al = a.length();
					int bl = b.length();
					for (int i = 0 ; i < Math.min(al, bl) ; i++) {
						if (a.charAt(i) < b.charAt(i)) {
							return -1;
						} else if (a.charAt(i) > b.charAt(i)) {
							return 1;
						}
					}
					return al - bl;
				}
			});
			base = b;
		}
		public int compareTo(S anothers) {
			int cmpsorted = compareList(slist, anothers.slist);
			if (cmpsorted == 0) {
				return compareList(ulist, anothers.ulist);
			}
			return cmpsorted;
		}
		
		public int compareList(List<String> arg0, List<String> arg1) {
			int min = Math.min(arg0.size(), arg1.size());
			for (int i = 0 ; i < min ; i++) {
				String a = arg0.get(i);
				String b = arg1.get(i);
				int c = comp(a, b);
				if (c != 0) {
					return c;
				}
			}
			return arg0.size() - arg1.size();
		}
	}
	
	
	public boolean[] v;
	
	public int comp(String a, String b) {
		int al = a.length();
		int bl = b.length();
		for (int i = 0 ; i < Math.min(al, bl) ; i++) {
			if (a.charAt(i) < b.charAt(i)) {
				return -1;
			} else if (a.charAt(i) > b.charAt(i)) {
				return 1;
			}
		}
		return al - bl;
	}
	
	public List<String> syllablize(String w) {
		List<String> sy = new ArrayList<String>();
		int l = w.length();
		int from = 0;
		boolean isv = false; 
		for (int i = 0 ; i < l ; i++) {
			if (!v[w.charAt(i)]) {
				if (isv) {
					sy.add(w.substring(from, i));
					from = i;
					isv = false;
				}
			} else {
				isv = true;
			}
		}
		sy.add(w.substring(from));
		return sy;
	}
	
	
	public String[] sortWords(String[] words) {
		v = new boolean[512];
		v['a'] = v['e'] = v['i'] = v['o'] = v['u'] = true;
		List<S> sylist = new ArrayList<S>();
		for (String w : words) {
			sylist.add(new S(syllablize(w), w));
		}
		Collections.sort(sylist);
		String[] ns = new String[words.length];
		for (int i = 0 ; i < words.length ; i++) {
			ns[i] = sylist.get(i).base;
		}
		return ns;
	}

}