第128回【Python】指定の位置への要素の追加

現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 128 回目です。

今回から、計算量について意識し始めた方にオススメのメニュー「クエリメニュー」に挑戦します。普段から計算量は意識しているつもりです。AWS Lambda の 15 分制限とよく戦っているので。ここで学んで、更に計算量を減らすことが出来れば、それだけ AWS Lambda が起動する時間を減らすことができ、結果として課金額を減らすことができるので、しっかり取り組みたいと思います。

それでは、今日も頑張ってみようと思います。

指定の位置への要素の追加

整数 N, K, Q と、 長さ N の配列 A_1, A_2, …, A_N が与えられるので、A_K の後ろに Q を挿入した後の長さ N+1 の配列について、先頭から改行区切りで出力してください。

N K Q
A_1
...
A_N

・1 行目では、配列 A の要素数 N と整数 K , Q が半角スペース区切りで与えられます。
・続く N 行では、配列 A の要素が先頭から順に与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100,000
・1 ≦ K ≦ N
・0 ≦ Q ≦ 100
・0 ≦ A_i ≦ 100 (1 ≦ i ≦ N)

入力例

3 1 57
17
57
83

出力例

17
57
57
83

Python では瞬時に思い浮かぶ insert 。しかし、VBA では面倒な処理を書かなければいけない気がする。

Python
N,K,Q = map(int,input().split())
A = [int(input()) for _ in range(N)]
A.insert(K,Q)
for a in A:
    print(a)

insert の計算量は O(N) で、効率的というわけではない。

VBA
Sub query_primer__single_insertion()

    s = Split(Cells(1, 1), " ")
    N = Val(s(0))
    K = Val(s(1))
    Q = Val(s(2))

    Dim A() As Integer
    ReDim A(N - 1)

    For i = 0 To N - 1
        A(i) = Cells(i + 2, 1)
    Next

    ReDim Preserve A(UBound(A) + 1)

    For i = UBound(A) To K Step -1
        A(i) = A(i - 1)
    Next

    A(K) = Q

    For Each v In A
        Debug.Print v
    Next
    
End Sub

最後に

まだ計算量を意識したコードにはなっていないです。次に挑戦する問題からは、計算量を意識しない方法と意識する方法、交互に挑戦していくみたいです。

しっかり勉強していきたいと思います。

引き続き、よろしくお願いいたします！

PythonPython,paiza,学習

Posted by LeoSaki