프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://school.programmers.co.kr/learn/courses/30/lessons/43165
[나의 풀이]
⌛ 16분
from collections import deque
def solution(numbers, target) :
answer = 0
length = len(numbers)
queue = deque([(1,numbers[0]),(1,numbers[0]*(-1))])
while queue:
v = queue.popleft()
cnt, value = v
if cnt!=length:
queue.append((cnt+1,value+numbers[cnt]))
queue.append((cnt+1,value+numbers[cnt]*(-1)))
else:
if value==target:
answer += 1
return answer
입력되는 배열(numbers)를 덧셈 혹은 뺄셈으로 조합하여 타겟(target)으로 만들 수 있는 경우의 수를 구하는 문제입니다.🦢🦢🦢
연산할 수 있는 경우의 수를 BFS를 활용하여 Queue구조에 (현재 갯수, 총합)을 append 하는 방식으로 구현하였습니다.
[다른 사람의 풀이1]
answer = 0
def DFS(idx, numbers, target, value):
global answer
N = len(numbers)
if(idx== N and target == value):
answer += 1
return
if(idx == N):
return
DFS(idx+1,numbers,target,value+numbers[idx])
DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
global answer
DFS(0,numbers,target,0)
return answer
재귀함수, DFS를 활용한 방식입니다. 🐪🐪🐪
재구함수 파라미터로 dfs(현재 갯수, 입력된 배열, 타겟 숫자, 총합)으로 설정하고 최대 갯수를 만족할 때마다 타겟 넘버인지 확인하는 방법입니다.
[다른 사람의 풀이2]
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
가장 간결하고 생각해내기 어려웠던 풀이입니다.🐨🐨🐨
'나의 풀이', '다른 사람의 풀이1'과 같이 BFS/DFS를 사용하지 않고 solution() 함수 자체를 재귀시켜 구현한 방식입니다.
재귀시키는 원리로 solution(입력 배열, 타겟)에서
'입력배열'을 'numbers[1:]'으로 표현하여 첫번째 요소를 제거하고 타겟에서 이를 빼거나 더해주는 식을 표현하여 경우의 수를 나누고 이를 반복하여
모든 입력배열이 제거되었을 때, target==0이라면 1가지 경우의 수를 찾은 것이므로 1을 return하고 아니라면 타깃을 만족하지 못하는 케이스로 0을 return하는 방식입니다.