コーディングしなさすぎてコーディングを忘れたエンジニアがコーディングを思い出すためにコーティングします。
今回は、アメリカのコーデイング練習サイトCodeSignalの問題「firstNotRepeatingCharacter」を解いていきます。
サイトによると、この問題はAmazonの面接で出されたことがあるようです。
問題
"abacabaed"のような文字列sが渡されるので、最初に出てくる重複していない文字を探します。
上の例だと、重複していないし最初に出てくるのでcが答えです。
もし重複している文字がない場合は、'_'を返します。
考え方・解説
最初は単純に、文字を一つずつループして、もう一つループを回して他の文字と比較し、重複がない文字を探す方法が浮かびました。
しかしこの方法で回答すると、実行時間超過でテストが一部通りませんでした。
そこで、この解き方の無駄を探すと、それぞれのループで全ての文字をチェックしていたので、重複した文字を何度も比較してしまっていることに気づきました。
たとえば、文字列の中にaが1000回あれば、2回目のaでその文字は重複しているため答えではないのがわかるのに、その後の997個のaも比較をしている、という具合です。
そこで、ループで重複が検知できたらループを即座に抜け、次の確認する文字に移るという回答に書き換えたところ、テストに通ることができました。
Javaで書くとこんな感じです。
char firstNotRepeatingCharacter(String s) {
boolean unique;
for (int i = 0; i < s.length(); i++) {
unique = true;
for (int j = 0; j < s.length(); j++) {
if (i != j && s.charAt(i) == s.charAt(j)) {
unique = false;
break;
}
}
if (unique) {
return s.charAt(i);
}
}
return '_';
}
コードの説明
2つのforは文字列の各文字を一つづつループしています。
1つめのifで2つのループそれぞれの文字を比較し、同じであればその文字は重複あり、つまり答えではないので、uniqueフラグをfalseにします。
と同時に、breakでループを抜け次の文字に移ります。
各文字がループし終わるたびに、2つめのifの部分で変数uniqueの結果を確認し、trueのままの文字があればそれは重複していなかったことを意味するので、答えとして返却します。
最後まで何も返却されなければ、重複なしのため'_'を返します。
感想
2つのループどちらもすべての文字をチェックするのは無駄かなとなにか改善しようと試みましたが、重複があればすぐにループがbreakされるので、結局問題ないようでした。
回答後、他の人の回答を見るともっと上手いやり方があって勉強になりました。
そのコードを載せるのは微妙なので仕組みだけ書くと、ループは一つで、各文字について文字列sの中で出現する位置を確認し、最初のインデックス（s.indexOf）と最後のインデックス（s.lastIndexOf）を取得します。
それらのインデックスが同じ値であれば、文字列の中に1個しか存在しないので、重複なし（＝答え）。
インデックスが異なれば、複数存在しているので重複あり（＝答えではない）、という感じでした。
自分にはまったく思い浮かびませんでした。
ネステッドループを無くすというアイデアをしつこく考えれば、もしかしたら思い付けたかもしれません。