[알고리즘/Python] 프로그래머스 - 타겟 넘버 (DFS)

프로그래머스 문제 설명

풀이1

• DFS 를 어떻게 이용할지 감이 안와서 비효율적으로 풀어버렸다.
• 가능한 케이스를 전부 고려해서 구현
• itertools.product 이용해서 곱집합 구하기

solution 함수의 파라미터와 리턴값은 다음과 같다.

• numbers : 사용할 수 있는 숫자가 담긴 배열
• target : 타겟 넘버
• return : 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수

자세한 풀이는 다음과 같다.

• product 함수를 통해 가능한 case 구하기 (cases 예시는 그림 참고)
• 덧셈과 뺄셈 연산을 할 수 있으므로 [-1, 1] 을 곱하는 값이라고 생각했다. 
• length 만큼 반복하며 case[i] * numbers[i] 를 더한 값이 target 과 같으면 count 를 증가시켰다.

from itertools import product

def solution(numbers, target):
    length = len(numbers)
    # 전체 가능한 case 구하기
    cases = []
    for _ in range(length):
        cases.append([-1, 1])
    cases = list(product(*cases))

    # target 인 경우만 count 하기
    count = 0
    for case in cases:
        s = 0
        for i in range(length):
            s += case[i] * numbers[i]
        if s == target:
            count += 1
    return count

print(solution([1, 1, 1, 1, 1], 3))

 

풀이2

• 프로그래머스의 DFS 를 이용한 풀이를 참고했다.
• 현재 값을 더하거나 빼는 과정에서 DFS 를 각각 호출한다.
  • 더한 값을 통해 DFS 재귀호출
  • 뺀 값을 통해 DFS 재귀 호출
• index 를 계산해 마지막 값을 더했을 때 종료되도록 한다.
• 종료되기 전에 더한 값이 target 과 같으면 answer 증가

answer = 0
def dfs(idx, numbers, target, value):
    global answer # 전역변수 사용한다는 선언

    length = len(numbers)
    # 전부 다 계산했을 때 target 과 같은 경우, 정답
    if(idx == length and target == value):
        answer += 1
        return
    # 전부 다 계산했을 때 target 과 다른 경우,
    if(idx == length):
        return 

    # 현재 값을 더하거나 빼서 value 로 설정, 다음 index 계산을 위해 dfs 반복
    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

print(solution([1, 1, 1, 1, 1], 3))

---

프로그래머스 링크

코딩테스트 연습 - 타겟 넘버

 

이번 문제를 풀면서

• 비효율적일지라도 첫번째 풀이는 스스로 풀어보도록 한다.
• 정답이더라도 다른 사람의 풀이를 보면서 코드를 고쳐나가자.
• DFS / BFS 관련 문제를 더 풀어보자.