プログラマ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
プロセス
その後BFSはqueue,DFSはstackを用いることが分かった.
図形は:{1:[1,−1],2:[1->1,1->−1,−1>1,...}
このように巡回する.
これを用いて,リスト内の値と深さレベルを組み合わせて,深さの末尾に達したときの和を区別するコードを記述した.
タイムアウトの問題で失敗しました
コード#コード#
ターゲット番号
問題の説明
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に変えて解決しました.Reference
この問題について(プログラマDFS/BFS LV 2), 我々は、より多くの情報をここで見つけました https://velog.io/@narangke3/프로그래머스-DFSBFS-LV2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol