1007 DNA Sorting

タイトルの意味は明らかで,各文字列の逆シーケンス数を算出し,それらの逆シーケンス数に従って並べ替え,最後に出力する.したがって、ここでの主な操作は2つのステップに分けられます.
 
①逆数の計算
ここに現れる文字は4種類しかないことに気づきました(ACGT)なので、文字列を一度スキャンすれば逆序数を算出することができる.方法は、文字列を順方向スキャンし、スキャン時にC、G、Tが出現した回数を記録し、現在スキャンしている文字がAであれば逆序数にC、G、Tの個数を順次加算し、Cであれば逆序数にG、Tの個数を加算し、Gであれば逆序数にTの個数を加算する.
 
②文字列を逆数で並べ替える
ここでは,逆シーケンス数が同じである場合,出現順にソートすること,すなわちソート結果が安定することが要求される.したがって,高速ソートの化を用いる場合は,逆シーケンス数を直接比較基準とすることはできないが,逆シーケンス数が同時に文字列の出現順序を比較基準とするなど,融通がきく.
Javaではオブジェクト配列のソートは安定している(具体的なアルゴリズム:JDK 7以前は集計ソートMergeSort、JDK 7ではTimSortを使用していた.時間があれば検討してみて、理解してほしい~).
 

import java.util.*;
import java.io.*;
//1007 DNA Sorting
public class Main 
{
	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(new BufferedInputStream(System.in));
		int countOfCase, lengthOfString;

		lengthOfString = in.nextInt();
		countOfCase = in.nextInt();

		DNA[] DNAs = new DNA[countOfCase];
		for(int i = 0; i < countOfCase; i++)
			DNAs[i] = new DNA(in.next());

		Arrays.sort(DNAs);

		for(DNA dna: DNAs)
			System.out.println(dna.strOfDNA);
	}
}

class DNA implements Comparable<DNA>
{
	String strOfDNA;
	int countOfInversion;

	public DNA(String strOfDNA) {
		this.strOfDNA = strOfDNA;
		calInversion();
	}

	private void calInversion() {
		countOfInversion = 0;

		int C = 0, G = 0, T = 0;
		for(int i = 0, n = strOfDNA.length(); i < n; i++) {
			switch(strOfDNA.charAt(i)) {
				case 'A':
					countOfInversion = countOfInversion + C + G + T;
					break;
				case 'C':
					C++;
					countOfInversion = countOfInversion + G + T;
					break;
				case 'G':
					G++;
					countOfInversion = countOfInversion + T;
					break;
				case 'T':
					T++;
					break;
			}
		}
	}

	public int compareTo(DNA another) {
		return countOfInversion - another.countOfInversion;
	}
}