타켓 넘버 (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에 대한 완벽한 이해는 하지 못했다.
- 하지만, 어떤 형식으로 탐색을 해야하는지 정도의 감은 잡혔다.
- 프로그래머스에 다른 문제들은 레벨이 높아 아직 도전하기엔 어려울 듯 하니 백준에서 같은 유형의 문제들을 더 풀어봐야겠다.
- 알고리즘 공부를 시작한 후로 명확한 해답을 내지 못했던 첫번째 문제!
Author And Source
이 문제에 관하여(타켓 넘버 (Programmers 43165)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@moonpiderman/타켓-넘버-Programmers-43165저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)