1. 問題提起
タイトルだけでは、何のことを言っているか伝わらないでしょう。
例えば、繰り返し構造のある文字列
ABCABC…
のなかに、
ABCAABC…
ABCACABC…
1つAが余っていたり、Bが抜けているような、エラーを見つけることです。
また、上記の例はリストで表せば、
[“A”, “B”, “C”, “A”, “B”, “C”…]
に相当します。
現実でありそうな例を挙げます。ある店で曜日ごとの売り上げを記録しているとき、通常は
月火水木金土日月火水木金土日…
という順番でデータが存在するはずですが、２週目の月曜日の記録を忘れて、
月火水木金土日 火水木金土日…
となってしまうような場合が考えられます。こういったエラー箇所を特定するのが本記事の目的です。
2. 考え方
まず、A, B, Cの３種類の要素を繰り返す理想的なデータなら
ABC ABC ABC…
と繰り返すはずです。
しかし
ABC ABC BC ABC A ABC
といった非理想的な並びを持つ場合があります。
これを判別するプログラムを考えます。
ポイント
AtCoder ABC122 C – GeT ACと類似した問題です。
「累積和」を応用して解決することができそうです。
つまり、前から１文字ずつ見ていったとき、“ABC”が何個完成しているかを記録していく
ということです。例えば、理想的なデータの場合、”C”が登場した時点で、完成する”ABC”が１つ増えます。
よって、
例1)
ABC ABC ABC…
001 112 223
の下の数字は、「文字列の先頭から見て、”ABC”が何個完成しているか」
という意味を持ちます。
では、非理想的な配列も見てみましょう。
例2)
ABC ABC BC ABC A ABC
001 112 22 223 3 334
と数え上げていくことになります。
以上より、文字列の情報を数字に置き換えることができました。
さて、エラーが発生している場所の特定に応用するにはどうしたらよいでしょうか。
- 例1)の理想的な場合では、連続する数字は3つまでです。
- 例2)を見ると、エラーの発生場所付近では、同じ数字が4つ以上連続していることが分かります。
したがって、この「同じ数字が３つ以上連続している場所」を特定して、
エラーとして返すプログラムを書けばよいと考えました。
以下がそのプログラムです。
3. 実装例
S = input()
N = len(S)
t = [0] * (N + 2) # 最後の2個に意味はない。index out of rangeを防ぐために用意。
for i in range(N):
# ABC が完成したら +1
if S[i : i + 3] == 'ABC':
t[i + 2] = t[i + 1] + 1
else:
t[i + 2] = t[i + 1]
cnt = 0
for i in range(N):
# 前の数字と同じ回数をカウント
if t[i + 1] == t[i]:
cnt += 1
else:
cnt = 0
# 3つ以上同じ数字が続いたらエラー
if cnt > 2:
print("error", i)これを実行すると、入力セルがでてくるので、任意の文字列を入力してみましょう。
※文字列の中の空白は、見やすさのために入れています。プログラムを動かす際には、スペースなしで入力する必要があります。
例えば、例2の
ABC ABC BC ABC A ABC
を入れてみると、
error 7
error 8
error 12
が返されます。
7, 8, 12文字目がエラーであることと一致します。
ABC C ABC C ABC C
error 4
error 8
ABC ABC BC BC A ABC A ABC
error 7
error 8
error 9
error 10
error 11
error 15
これで、規則的な繰り返し構造の中に含まれる、不規則な部分を発見することができました！
最後に
A, B, Cの色々な並びに対応できているか、精査する必要はあるかもしれません。
しかし、発想としては、面白いものができたのではないかと思います。
ABC C ABC C ABC Cの最後のCのように、最後に１つだけ余った文字がある場合、対応
できないという難点もあります。
しかし、文字列の最後に”ABC”を付け足せば、解決できるでしょう。
実際のデータに適用してみて、エラー箇所を探せるか試し、場合によっては修正が必要かもしれません。
コメント