CodeIQ：文字列を五十音順に並び替えてみよう（修正版）

問題を引用します。

あなたはとある名簿管理ツールの開発者で、名前の表示順序を決めるアルゴリズムを任されました。
最も実装が容易なのは文字コード順ですが、国語辞典のように、日本のJIS規格で定められた日本語文字列照合順番、いわゆる五十音順に沿ってほしいとのこと。
ユーザーの利便性を考えるなら、避けては通れそうにありません。

求められるプログラムの前提条件は、以下の通りとなります。

標準入力から、改行区切りでN個の文字列が送られる。Nは10以下、各文字列の長さも10以下とする
文字列は訓令式ローマ字のみで構成されており、半角小文字の英文字のみ使われる
訓令式ローマ字以外の文字（ヘボン式ローマ字特有の表現や、記号や全角文字など）は含まれない
訓令式ローマ字の中で重複が認められる文字について、"i/u/e/o"は「あ」行の「い/う/え/お」、"z"から始める文字は「ざ」行として解釈すること
これらN個の文字列に対し、その読み仮名から日本語文字列照合順番でソートすること
ソート順が同一の文字列を含むような、順序が一意に定まらないパターンは入力に含まれないため考慮しなくともよい
求めたN個のソート済み文字列を、改行区切りで標準出力で返すこと

改めて、本設問におけるローマ字と、ソートの基準となる読みの対応を以下の表で示します（Wikipediaより一部抜粋）

	あ	い	う	え	お	（拗音）
あ	a	i	u	e	o
か	ka	ki	ku	ke	ko	kya	kyu	kyo
さ	sa	si	su	se	so	sya	syu	syo
た	ta	ti	tu	te	to	tya	tyu	tyo
な	na	ni	nu	ne	no	nya	nyu	nyo
は	ha	hi	hu	he	ho	hya	hyu	hyo
ま	ma	mi	mu	me	mo	mya	myu	myo
や	ya		yu		yo
ら	ra	ri	ru	re	ro	rya	ryu	ryo
わ	wa
が	ga	gi	gu	ge	go	gya	gyu	gyo
ざ	za	zi	zu	ze	zo	zya	zyu	zyo
だ	da			de	do
ば	ba	bi	bu	be	bo	bya	byu	byo
ぱ	pa	pi	pu	pe	po	pya	pyu	pyo

しゃ sha	し shi	しゅ shu	しょ sho
		つ tsu
ちゃ cha	ち chi	ちゅ chu	ちょ cho
		ふ fu
じゃ ja	じ ji	じゅ ju	じょ jo
	ぢ di	づ du
ぢゃ dya		ぢゅ dyu	ぢょ dyo
くゎ kwa
ぐゎ gwa
			を wo

五十音順について、本設問で適用されるルールは以下の通りです。
（Wikipediaより一部抜粋。なお平仮名はローマ字として扱ってください）

1.仮名に対し、次のように置き換える
「ぁ」「ゃ」「っ」などの小書き文字はその基底文字である「あ」「や」「つ」などに置き換える
「が」「ば」などの濁点付き文字はその基底文字である「か」「は」などに置き換える
「ぱ」「ぴ」などの半濁点付き文字はその基底文字である「は」「ひ」などに置き換える

2.上記置き換えて出来た文字列について、文字列の先頭より次の順序で比較して先にあるものが先になるように並び替える。
「あ」「い」「う」「え」「お」「か」「き」「く」「け」「こ」「さ」「し」「す」「せ」「そ」「た」「ち」「つ」「て」「と」「な」「に」「ぬ」「ね」「の」「は」「ひ」「ふ」「へ」「ほ」「ま」「み」「む」「め」「も」「や」「ゆ」「よ」「ら」「り」「る」「れ」「ろ」「わ」「を」「ん」

3.上記で文字列の並び替えを行った後、一致する順位となる文字列は、次のルールで並べる。
清音文字→濁点付き文字→半濁点付き文字
長音符→小書き文字→通常文字

それでは、入力と出力例を示しましょう。 ローマ字を平仮名に置き換えて表すと、「ひよう」「ひょう」「びよう」「ひよこ」という入力に対し、「ひょう」「ひよう」「びよう」「ひよこ」と出力するのが正しいことがわかりますね。

入力	出力（文字コード順・不正解）	出力（五十音順・正解）
hiyou hyou biyou hiyoko	biyou hiyoko hiyou hyou	hyou hiyou biyou hiyoko

なお、Pythonで文字コード順でソートするだけなら、次のコードで解決します。

import sys

for s in sorted(sys.stdin.read().strip().split('\n')):
    print(s)

それでは、五十音順でソートするにはどうすればよいでしょうか？
なお、プログラミングに用いる言語は何を用いても構いません。 是非挑戦してみてくださいね。

【問題】
標準入力から、改行区切りでN個の文字列が送られます。
文字列はいずれも訓令式ローマ字のみで構成されています。
これらを、JIS X 4061で定められた日本語文字列照合順番（五十音順）にソートし、そのソート済み文字列を改行区切りで標準出力に返してください。

考え方

ローマ字を平仮名に直してしまい、それを仕様に従ってソートするだけです。
ただし、これはUTF-8で扱えることを前提としているからできることで、Rubyでも文字コードがSJISの場合やC/C++の場合は平仮名ではなく数値に変換する方が楽です。

makePattern()

金将を振った時に進めるマス数のパターンを列挙します。
単純に金将が4つあって、1枚につき[0,1,5,10,20]のパターンがあるので全組み合わせを列挙し、重複を削除すれば良いだけです。
全部裏の場合は8と特殊な扱いになっていますが、他にも8の場合があるので0として扱ってしまいます。逆にコマが盤から落ちた場合など進めるマス数が0になる場合をこれでカバーしてしまいます。

StrDataクラス

ソート用に変換した文字列を保持するためのクラスです。
メンバ変数はそれぞれ次の役割になっています。

org	元のローマ字
kana	平仮名に変換した文字列
kitei	基底文字だけの平仮名に変換した文字列
dakuon	小書き文字は基底文字、濁音と半濁音はそのままにした文字列

コンストラクタではそれぞれのメンバ変数をセットします。

StrData#transKana()

ローマ字を平仮名に変換します。
日本語は基本的に母音がつくのでローマ字を先頭から1文字ずつ解釈し、母音が出た場合にそこまでを一区切りとして平仮名に変換することができます。
例外の一つはnの場合で、な行なのか「ん」なのかを判断する必要があります。これはnの次に"a", "i", "u", "e", "o", "y"がくるかどうかで判断します。
もう一つが小さい「つ」の場合で、これは子音が2つ連続した場合になりますので、これも判断します。

処理としてはローマ字の文字を1文字取り出し（64〜86行目）、bufにとります（65行目）。次の文字を取り出して母音ならそこまでを平仮名に変換します（66〜69行目）。取り出した文字がnの場合、次の文字を見て"a", "i", "u", "e", "o", "y"ならbufにとり、そうでなければ「ん」なので平仮名に変換します（70〜77行目）。それ以外の場合で子音が連続している場合は「っ」が入るので結果に「っ」を付加し、そのアルファベットは無視します。何でもない場合はbufにアルファベットを加えます。

StrData#toPattern()

平仮名に変換した文字列から基底文字だけの文字列と小書き文字だけを基底文字にした文字列（濁音、半濁音はそのままにする）を作ります。
これは定数DAKUON、KOGAKIが変換テーブルになっているのでそれを利用して変換するだけです。

StrData#compare()

仕様に従って比較する関数です。
仕様通りにkitei（基底文字同士）を比較し、違えば大小を返します。
同じならdakuon（小書き文字だけを基底文字にしたもの）を比較し、違えば大小を返します。
それも同じならkana（ローマ字を平仮名に直したもの）を比較して大小を返します。

toStrDataArray()

入力値を一つずつStrDataのインスタンスにし、配列にして返します。

printResult()

StrDataのインスタンスの配列をソートし、StrData#orgをソート順に印字します。
ソートはStrData#compare()に従うのでソート順はStrData#compare()を参照してください。