0
li = ['1','2','3','4','5']

これの文字列を
1,2,3をAに、4,5をBに効率よく置き換える方法はありますか?

補足
リストの右側 - リストの左側 = 3になった時に
リストの左側をA, リストの右側をBにしたいです。
これらは、連続してなければいけません。

left = 0
total = sum(li)
for i in li:
    left += i
    if total - left == 3:
        ??????

という感じで???で詰まっています。

4
  • 1
    書き換える規則のような物はあるのでしょうか?ひとまず、効率が悪くても良いので、あなたの今のコードを示さないことには何が目標なのか見えてきません。このままでは「li[:] = ['A', 'A', 'A', 'B', 'B']と置き換える」といった回答しかしようがないと思います。
    – raccy
    Commented 2020年6月20日 7:07
  • 1
    もう一つ「効率よく」というのはどのような意味ですか?この言葉は曖昧で、「コードが短く分かりやすい」という意味で使う人もいれば、「速度が最速」や「メモリ使用量が最低限」という意味で使う人もいます。「効率よく」をもっと具体的な表現で表してください。このままでは、曖昧なため閉じる票をいれられてもおかしくありません。
    – raccy
    Commented 2020年6月20日 7:09
  • コメントありがとうございます。効率よくというのは、計算量を少なくという意味でした。具体的に補足をしたので見ていただけたら幸いです。
    – sapcal000
    Commented 2020年6月20日 7:26
  • ちなみに「計算量」にも「時間計算量」や「空間計算量」など種類があります(ややこしいですね……)
    – nekketsuuu
    Commented 2020年6月20日 11:41

2 件の回答 2

2

下は時間計算量と空間計算量はともにO(n)です。差が3になる区切りが存在しない場合は、配列を変更しないとしています。

li = ['1','2','3','4','5']
total = sum(int(n) for n in li)
if total >= 3 and total % 2 != 0:
    half3 = (total - 3) // 2
    part_total = 0
    for idx, n in enumerate(li):
        if part_total == half3:
            li[:] = ['A'] * idx + ['B'] * (len(li) - idx)
            break
        elif part_total > half3:
            break
        part_total += int(n)

print(li)

途中で長さlen(li)の配列を作ってしまっているので、これをなくせば空間計算量をO(1)にすることもできます。ただし、ちょうど3になるかを判定するための部分が必要になります。少し妥協して、下は、差が3以下になるところで区切りを入れています。(ちょっとあやしい)

li = ['1','2','3','4','5']
total = sum(int(n) for n in li)
half3 = (total - 3) / 2
part_total = 0
for idx, n in enumerate(li):
    if part_total < half3:
        li[idx] = 'A'
    else:
        li[idx] = 'B'
    part_total += int(n)

print(li)

なお、計算量が少ない=高速・低メモリではないことに注意してください。与えられた配列の大きさに応じてどれぐらいの時間やメモリが消費するのかの目安にしか過ぎません。与えられる配列が小さい、または、一定の大きさ以下である場合は、逆に遅かったりメモリ消費が大きかったりしますのでご注意ください。

2
  • 1
    +1: 最初に全体の合計を求めておけば左側の合計値が分かるので切れ目も分かる、という方針が分かりやすかったです。ただし、時間計算量が少ない、というのは高速であることを意味します。らっしーさんがおっしゃっているのはO記法などで漸近的な表記をした後比較をするときの話になっていそうです。
    – nekketsuuu
    Commented 2020年6月21日 9:48
  • 1
    空間計算量の定義はいくつかありますが、入力も空間に含める数え方だと後者のプログラムも文字列長 n について空間計算量 O(n) になっています。前者もリストの書き換えを in-place にすれば後者とほぼ同じ空間計算量になりますが、この程度であればそこまで改善しなくて良いかもですね。
    – nekketsuuu
    Commented 2020年6月21日 9:53
1

リストの右側 - リストの左側 = 3になった時に

「(リストの右側の合計) - (リストの左側の合計) = 3になった時に」ですね。
以下のコードで実現できると思います。

li = ['1','2','3','4','5']
lin = [int(x) for x in li] #数値のリストに変換
n = 3
len_li = len(li)
for i in range(len_li):
    if sum(lin[i:]) - sum(lin[0:i]) == n:
        result = ['a'] * i + ['b'] * (len_li-i)
        break
else:
    result = ""

このコードは3に一致しなかったとき空文字列を結果としています。


上の例では左右の部分リストの合計を毎回最初から計算していますので、以下のコードの方が計算の量は少ないです。

li = ['1','2','3','4','5']
lin = [int(x) for x in li] #数値のリストに変換
n = 3
len_li = len(li)
sum_left = 0
sum_right = sum(lin)
for i in range(len_li):
    if sum_right - sum_left == n:
        result = ['a'] * i + ['b'] * (len_li-i)
        break
    sum_left += lin[i]    
    sum_right -= lin[i]    
else:
    result = ""
1
  • ありがとうございます。sumとスライスを使うのは思いつきませんでした!
    – sapcal000
    Commented 2020年6月20日 10:28

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。