[프로그래머스][Lv.2][Python] 타겟 넘버

1. 문제 (레벨 2)

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

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

 

2. 접근 방식

• BFS/ DFS 카테고리에 있는 문제지만, 해당 탐색 알고리즘으로 해결할 방법이 떠오르지 않아 완전탐색으로 구현
• +, - 부호를 이진수로 표현하여 모든 경우에 대해 연산한 뒤 개수를 카운팅함
• 통과는 했지만 메모리와 시간에 제한이 있다면 실패할 듯 함

 

3. 코드

def solution(numbers, target):
    answer = 0
    aa = pow(2, len(numbers))
    
    list_tmp = []
    list_arr = []
    
    for n in range(0, aa):
        tmp = n
        list_tmp = []
        
        while tmp > 0:
            list_tmp.append(tmp%2)
            tmp //= 2
            
        while len(list_tmp) < len(numbers):
            list_tmp.append(0)
         
        list_arr.append(list(reversed(list_tmp)))
        
        
    int_sum = 0    
    for tmp in list_arr:      
        int_sum = 0  
        
        for i in range(0, len(numbers)):
            if tmp[i]:
                int_sum += -1*numbers[i]
            else:
                int_sum += numbers[i]
        
        if int_sum == target:
            answer += 1
          
    
    return answer

 

4. 결과