프로그래머스 - 타겟넘버

프로그래머스의 코딩테스트 고득점 Kit의 DFS/BFS유형 문제들 중 Level 2 ‘타겟넘버’를 풀어보았습니다.

프로그래머스 - ‘타겟넘버’ 문제 보러 가기 !
https://programmers.co.kr/learn/courses/30/lessons/43165

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

문제 접근 방식

이번 문제는 조합 방식을 이용하여 풀 수 있다.
주어진 배열에서 덧셈 뺄셈으로 조합할 수 있는 모든 경우의 수를 구해야 한다. 이 경우들 중 합이 target과 같을 때 카운트를 1씩 증가해준다.

예를 들어,
number = [1,2,3] 이 주어진다면, 조합할 수 있는 모든 경우의 수는
1) [+1+2+3] = 6
2) [+1+2-3] = 0
3) [+1-2+3] = 2
4) [-1+2+3] = 4
5) [+1-2-3] = -4
6) [-1+2-3] = -2
7) [-1-2+3] = 0
8) [-1-2-3] = -6 이 된다. 이때 target이 0 이라면 카운트는 2가 된다.

이러한 접근 방식으로 풀어나갈 수 있다.

일단 모든 조합을 구하는 방식에는 아래의 두가지 방법이 있다.

1. dfs

일단 dfs방식으로 풀어보자.
처음에는 일반적인 dfs방식처럼 원본 데이터는 유지하며 매번 새로운 배열을 생성하고 visited 배열로 방문여부를 검사하여 덧셈과 뺄셈으로 조합한 리스트를 검증해야 한다고 생각했다.
그러나 이번 경우는 덧셈과 뺄셈 두가지 경우만 구해주면 되기에, 아래와 같이 처음부터 두가지로 나누어 dfs를 진행하면 될 것이다.

1. numbers[i] *= 1
dfs(i + 1)

2. numbers[i] *= -1
dfs(i + 1)

2. itertools의 product

파이썬에서 리스트에 있는 값들의 모든 조합을 구하기 위해선 여러가지 방법이 있다. 하지만 각각의 차이점을 알고 있어야 한다.

from itertools import product
from itertools import permutations
from itertools import combinations

• 하나의 리스트에서 모든 조합을 계산해야 한다면, permutations, combinations를 사용

items = ['1', '2', '3', '4', '5']
from itertools import permutations
list(permutations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '1'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '1'), ('3', '2'), ('3', '4'), ('3', '5'), ('4', '1'), ('4', '2'), ('4', '3'), ('4', '5'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4')]

from itertools import combinations
list(combinations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]

• 두개 이상의 리스트에서 모든 조합을 계산해야 한다면, product를 사용

from itertools import product

items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))
# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]

풀이 코드

1. dfs

def solution(numbers, target):
    answer = 0

    def dfs(i=0):
        if (i < len(numbers)):
            numbers[i] *= 1
            dfs(i + 1)

            numbers[i] *= -1
            dfs(i + 1)

        elif (sum(numbers) == target):
            nonlocal answer
            answer += 1

    dfs()
    return answer

1. product

from itertools import product

def solution2(numbers, target):
    all_case = [(x, -x) for x in numbers]
    sum_all = list(map(sum, product(*all_case)))
    return sum_all.count(target)