プログラマDFS/BFS LV 2


プログラマDFS/BFS LV 2
ターゲット番号
問題の説明
n個の非負の整数がある.順序を変更せずにこれらの整数を適切に追加または減算してターゲット番号を作成したいと思います.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.
//////////////////////////
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
//////////////////////////
使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.
せいげんじょうけん
与えられた数字の個数は2個または20個以上である.
各数字は1または50以下の自然数です.
ターゲット番号が1または1000以下の自然数です.
I/O例
numbers / target /return
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2
I/O例説明
I/O例#1
問題の例を以下に示します.
I/O例#2
+4+1-2+1 = 4
+4-1+2-1 = 4
プロセス
def solution(numbers, target):
    answer = 0
    Q=[]
    Q.append([numbers[0],0])
    Q.append([numbers[0]*-1,0])
    
    while Q :
        tmp, idx = Q.pop(0)
        idx+=1
        if idx < len(numbers):
            Q.append([tmp+numbers[idx],idx])
            Q.append([tmp-numbers[idx],idx])
        else :
            if target == tmp : answer+=1
                
                
    return answer
bfs dfsの概念と気まずいため,最終的にgooglingによってヒントを得た.
その後BFSはqueue,DFSはstackを用いることが分かった.
図形は:{1:[1,−1],2:[1->1,1->−1,−1>1,...}
このように巡回する.
これを用いて,リスト内の値と深さレベルを組み合わせて,深さの末尾に達したときの和を区別するコードを記述した.
タイムアウトの問題で失敗しました
コード#コード#
from collections import deque

def solution(numbers, target):
    answer = 0
    Q=deque()
    Q.append([numbers[0],0])
    Q.append([numbers[0]*-1,0])
    
    while Q :
        tmp, idx = Q.popleft()
        idx+=1
        if idx < len(numbers):
            Q.append([tmp+numbers[idx],idx])
            Q.append([tmp-numbers[idx],idx])
        else :
            if target == tmp : answer+=1
                
                
    return answer
QをDequeに変えて解決しました.