###問題
問題リンク
(概要)
長さnの英小文字列sが与えられ、そこから最終的にちょうどk文字を取り除きたい。取り除く順番のルールは、まずaが存在する限り左から取り除く。aがなくなったらbが存在する限り左から取り除く。bがなくなったら…。yがなくなったらzが存在する限り左から取り除く。といった手法を用いる。最終的に得られるsはどのようなものか。
#コード
Python
1n, k = map(int, input().split()) 2s = list(str(input())) 3 4length = 0 5li = [] 6for i in range(97, 97 + 26): 7 for j in range(n): 8 if s[j] == chr(i): 9 li.append(j) 10 length += 1 11 if length == k: 12 break 13 else: 14 continue 15 break 16 17li = set(li) 18 19ans = '' 20for i in range(n): 21 if i not in li: 22 ans += s[i] 23 24print(ans)
#方針
aからzの順に、かつ左から右の順に、取り除かれる要素のインデックスをリストliに追加していき、最後はそのli(setに変換後)にインデックスが含まれていないものだけを文字列ansに追加していき出力する。
#疑問
制限時間は2秒となっており、10^8回程度の計算は耐えられるかなと思い、nが高々4×10^5であることに鑑みて、a-zとの二重ループでも問題はないだろうという風に鷹を括っていたのですが、どの部分が具体的に計算時間を増幅させてしまっているのでしょうか。それとも、そもそもの話としてもう少し余裕をもったコードに書き換えた方が良いのでしょうか(その場合は一から考え直すのですが…)。素人質問にて恐縮ですが、お力添えいただける点がございましたら、何卒よろしくお願い申し上げます。
回答4件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2021/12/09 15:13
2021/12/09 15:14
2021/12/09 15:18 編集
2021/12/09 15:21
2021/12/09 15:26
2021/12/09 15:28