프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
나의 풀이
- 기존에 DFS, BFS를 시뮬레이션에서만 활용했어서 간단한 문제임에도 못 풀었다.
- DFS를 활용할 때, 어떤 값을 넘겨줄 지가 정확히 설계하는 것이 중요함을 깨달았다.
- DFS를 재귀, stack 방식 모두를 활용해 구현해봤다.
from collections import deque
def dfs(num_sum: int, idx: int, max_idx: int, numbers: list, target: int):
global answer
# DFS 진행 동안 answer 값 증가
if idx == max_idx:
if num_sum == target:
answer += 1
return
dfs(num_sum + numbers[idx], idx + 1, max_idx, numbers, target)
dfs(num_sum - numbers[idx], idx + 1, max_idx, numbers, target)
# 최종적인 answer 반환
return answer
def solution(numbers, target):
global answer
answer = 0
answer = dfs(0, 0, len(numbers), numbers, target)
return answer
from collections import deque
def dfs(numbers, target):
cnt = 0
queue = deque()
# +, - 시작
queue.append([numbers[0], 0])
queue.append([-numbers[0], 0])
while queue:
# stack 처리
val, idx = queue.pop()
idx += 1
if idx < len(numbers):
queue.append([val +numbers[idx], idx])
queue.append([val -numbers[idx], idx])
else:
if val == target:
cnt += 1
return cnt
def solution(numbers, target):
answer = dfs(numbers, target)
return answer
참고
