[파이썬] 프로그래머스 : 타겟 넘버 (Lv.2)

[파이썬] 프로그래머스 : 타겟 넘버 (Lv.2)

프로그래머스

---

풀이

0.방향성 생각

• 리스트 길이가 20 이하이다. 2**20 = 10만이라 잡으면 완탐으로도 충분히 가능

1. 중복 순열

from itertools import product as P

def solution(numbers,target):
    answer = 0
    leng = len(numbers)
    for i in P([1, -1], repeat=leng):
        if sum(map(lambda x,y: x*y, numbers,i)) == target:
            answer += 1
    return answer

• (1,-1) 을 중복으로 선택해서 입력 리스트와 길이가 같게 만든 뒤 각 요소를 곱함.(내적) 
• 실제 P를 객체에 할당하는거보다 빠르지만 그래도 좀 느린감이 있다.

2. BFS

from collections import deque

def solution(numbers,target):
    
    answer = 0
    q = deque([(0,0)])
    while q:
        x,stage = q.popleft()
        
        if stage == len(numbers) and x == target:
            answer += 1
            
        if stage < len(numbers):
            for i in (numbers[stage],-numbers[stage]):
                q.append((x+i,stage+1))
            
    return answer

• 응애시절에 푼 풀이.
• 리스트 요소를 전부 더한 후, 타겟넘버가 됐으면 +1

3. DFS

def solution(numbers, target):
    
    answer = 0
    leng = len(numbers)

    def dfs(count,goal):
        
        nonlocal answer

        if count == leng:
            if goal == target:
                answer += 1
            return

        for i in (numbers[count],-numbers[count]):
            dfs(count+1, goal+i)

    dfs(0,0)
    return answer

• 백준 풀었을 땐, global로 했는데, 함수 내부에서 진행하려고 하다보니까 nonlocal로 써야한다는걸 알았음
• 재귀야 뭐 항상 똑같이. 탈출조건 걸어줘야함.
• 리스트 요소 전부 더했고, 타겟넘버 도달했으면 +1 아닌 경우에는 탈출만 시켜줘서 루프 발생 안하게

---

 

코멘트

.