프로그래머스 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

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

문제 설명

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

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

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

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

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

풀이:

두가지의 완전 탐색 방법으로 문제를 풀었다. 한개는 dfs 로 완전탐색을 한거고, 두번째는 데카르트 곱으로 순서쌍의 합을 통한 완전 탐색이다. 

사실 둘다 최악의 경우 2^20 이 나와서 꺼려졌다. 이런 문제들은 솔직히 불편하다. 완전 탐색 문제면 최악의 시간 복잡도를 좀 여유를 주어서 완전탐색으로 풀 수 있다는 클루를 줘야 한다고 생각한다. 

파이썬에서 for i in range(2^20): pass 돌리면 절대 주어진 시간 내에 해결되지 않는다. 

 

별개로, 문제를 풀면서 느낀 건 아이디어 구현이 아직 부족하다는 것인데, 다음의 두가지 이유때문이다. 

1) dfs로 푼다고 할 때, 멍청하게도 기존 유형의 문제들을 생각하며 어떻게 대입할 수 있을까 고민하였다. 한마디로 알고리즘을 알아도 어떻게 언제 적용할지에 대한 감이 없는 듯 해서 생각보다 심각한 문제로 보였다. 문제를 많이 풀어야 한다고 느꼈다. 

 

2) product 를 직접 구현하려고 하니까 3중 for 문 돌리는 것이 꺼려졌다. 그럼에도 실제 코딩테스트에서 만났다면 구현해야 할텐데, 자꾸 효율적인 방법만 찾는게 오히려 안 좋을 수 있다는 생각이든다. product 무듈은 잊지 말자. 

 

def solution(numbers, target):    
    
    answer = dfs(numbers, target, 0, 0)
    return answer

def dfs(numbers, target, i , n ): 
    answer = 0
    if i == len(numbers):
        if n == target:
            return 1 
        else: return 0
    answer += dfs(numbers, target, i+1, n+numbers[i])
    answer += dfs(numbers, target, i+1, n-numbers[i])
    return answer

재귀를 돌면서 element 를 1개씩 추가 방문한다, 모든 element를 방문 했을 때 target 값과 같다면 +1 다르면 +0 

from itertools import product
def solution(numbers, target):    
    nums = [(x, -x) for x in numbers]
    answer = list(map(sum , product(*nums)))

    return answer.count(target)

간단하게 주어진 element들의 두가지 부호에 대하여 데카르트 곱으로 모든 순서쌍을 생성한 후, map 함수로 각 순서쌍의 합을 만들고, count 함수로 개수를 세서 반환하는 함수이다. 

 

시스템을 생각하지 않고 논리로만 따지면 sum을 하고, list화하고, count까지하는 아래의 알고리즘이 시간복잡도가 더 높을 것 같지만 실제 결과는 정 반대로 나왔다. 역시 재귀를 사용하면 시간이 오래걸린다. 데카르트 곱의 이용이 모든 테스트 케이스에서 압도적으로 빠르다.