[프로그래머스] Level 2_타겟넘버(BFS/DFS)

📌문제유형

BFS/DFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 하단의 문제풀이로 풀이

• tmp에 양수, 음수 모든 경우의 수로 숫자 더해서 넣기
• tmp를 leaves에 대입
• leaves를 탐색하며 target과 맞는지 확인

프로그래머스 - 타겟 넘버 (DFS, BFS) Python

#BFS 풀이
def solution(numbers, target):
    answer = 0
    leaves = [0]
    
    # 모든 경우의 수 다 더하는 것
    for num in numbers:
        tmp = []
        for parent in leaves:
            tmp.append(parent + num)    # 양수로 tmp에 넣기
            tmp.append(parent - num)    # 음수로 tmp에 넣기
        leaves = tmp    # leaves를 tmp로 대체
        
    # 모든 경우의 수가 target과 맞는지 확인
    for leaf in leaves:
        if leaf == target:
            answer += 1
            
    return answer

 

📌다른 사람의 문제풀이

1) 재귀 사용

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

2) product(데카르트 곱)을 이용한 풀이

•  product : DB의 join과 유사
  • 두 개 이상 리스트의 모든 조합을 구할 때 사용
• map : 여러 개의 데이터 -> 한 번에 다른 형태로 변환
  • map(변환 함수, 순회 가능한 데이터)

Python 순열, 조합, product - itertools

 

파이썬 map 내장 함수 사용법 (feat. List Comprehension)

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    
    return s.count(target)

 

3) DFS 이용

 - answer는 global 이용하여 전체 값 바뀌게 하기

answer = 0

def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return
        
    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

 

📌리뷰

- 전체 경우의 수 따질 때 : BFS, DFS, product(*리스트) 사용하기