💡코딩테스트/프로그래머스
[프로그래머스 | 파이썬 python] 타겟 넘버
두_두
2023. 5. 16. 16:10
깊이/너비 우선 탐색(DFS/BFS)
🌏 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 풀이 -- BFS 사용
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque()
queue.append([numbers[0],0])
queue.append([-numbers[0],0])
while queue:
temp ,idx = queue.popleft()
idx += 1
if idx < len(numbers):
queue.append([temp+numbers[idx],idx])
queue.append([temp-numbers[idx],idx])
else:
if temp == target:
answer += 1
return answer
👽 풀이 -- DFS 사용
def solution(numbers, target):
global answer
answer = 0
def dfs(n, idx):
global answer
if idx == len(numbers) and n == target:
answer += 1
if idx < len(numbers):
dfs(n + numbers[idx] ,idx+1)
dfs(n - numbers[idx] ,idx+1)
dfs(0,0)
return answer
728x90