프로그래머스 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하는 방식입니다.