ターゲット番号(Programmers 43165)

🧑‍💻 質問する

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

使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.
せいげんじょうけん

で与えられた数字は20個未満です.

各数字

は50より大きい自然数である.

目標は自然数が1000より大きいことです.

I/O例
numberstargetreturn[1, 1, 1, 1, 1]35

🧑‍💻 解決策

カテゴリに沿ってDFSまたはBFSを使用して解凍する必要があります.

スタックまたはキューを使用して問題を解決できます.

🧑‍💻 DFS & BFS

from collections import deque
def bfs(graph, start_node) :
   visit = list()
   queue = list()
   queue.append(start_node)
   queue = deque(queue)
   while queue :
       node = queue.popleft()
       if node not in visit :
           visit.append(node)
           queue.extend(graph[node])

   return visit
def dfs(graph, start_node) :
   visit = list()
   stack = list()

   stack.append(start_node)

   while stack :
       node = stack.pop()
       if node not in visit :
           visit.append(node)
           stack.extend(reversed(graph[node]))

   return visit

if __name__ == '__main__' :
   graph = {
       'A': ['B'],
       'B': ['A', 'C', 'H'],
       'C': ['B', 'D'],
       'D': ['C', 'E', 'G'],
       'E': ['D', 'F'],
       'F': ['E'],
       'G': ['D'],
       'H': ['B', 'I', 'J', 'M'],
       'I': ['H'],
       'J': ['H', 'K'],
       'K': ['J', 'L'],
       'L': ['K'],
       'M': ['H']
   }

   print(bfs(graph, 'A'))
   print(dfs(graph, 'A'))
   # 출력결과
   #['A', 'B', 'C', 'H', 'D', 'I', 'J', 'M', 'E', 'G', 'K', 'F', 'L']
   #['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M']

幅優先ナビゲーションDFSには、深度優先ナビゲーションの結果が表示されます.

🧑‍💻 コード#コード#

from collections import deque

def solution_stack(numbers, target) :
   answer = 0
   length = len(numbers)
   stack = []

   stack.append([numbers[0], 0])
   stack.append([-1 * numbers[0], 0])

   while stack :
       total, index = stack.pop()
       index += 1
       if length > index :
           stack.append([total + numbers[index], index])
           stack.append([total - numbers[index], index])
           print(stack)
       else :
           if total == target :
               answer += 1
   return answer

def solution_queue(numbers, target):
   answer = 0
   length = len(numbers)
   queue = deque()

   queue.append([numbers[0], 0])
   queue.append([-1 * numbers[0], 0])

   while queue :
       total, index = queue.popleft()
       index += 1
       if length > index :
           queue.append([total + numbers[index], index])
           queue.append([total - numbers[index], index])
           print(queue)
       else :
           if total == target :
               answer += 1
   return answer

if __name__ == '__main__' :
   numbers_1 = [1, 1, 1, 1, 1]
   target_1 = 3
   print(solution_stack(numbers_1, target_1))
   print(solution_queue(numbers_1, target_1))

🧑‍💻 総評

DFS、BFSを完全に理解していない.

ですが、どのような形で探索すべきかについては、すでに一定の感覚があります.

プログラマーの他の問題はレベルが高く、まだ挑戦しにくいので、同じタイプの問題を白準で多く解く必要があります.

アルゴリズムの学習を開始してから、最初に明確な答えを与えなかった問題!