타켓 넘버 (Programmers 43165)

🧑‍💻 문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.
예를 들어 [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
• +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

🧑‍💻 해결방법

• 카테고리를 따라 DFS 혹은 BFS로 풀어야한다.
• stack이나 queue를 활용하여 문제를 해결할 수 있다.

🧑‍💻 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']

BFS는 '너비우선탐색' 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에 대한 완벽한 이해는 하지 못했다.
• 하지만, 어떤 형식으로 탐색을 해야하는지 정도의 감은 잡혔다.
• 프로그래머스에 다른 문제들은 레벨이 높아 아직 도전하기엔 어려울 듯 하니 백준에서 같은 유형의 문제들을 더 풀어봐야겠다.
• 알고리즘 공부를 시작한 후로 명확한 해답을 내지 못했던 첫번째 문제!