[Python] 프로그래머스 - 타겟넘버

1. 프로그래머스 - 타겟넘버 / 문제 유형 : bfs / Level 2

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

프로그래머스

bfs/dfs를 연습하기 위해 고득점 kit bfs/dfs 중 풀어본 문제다.

생각보다 간단한 문제로 간단한 설명은 아래 사진을 참고하면 된다. 

문제를 풀어보고 싶다면, 위에 링크를 눌러 확인하면 된다.

[출처] 프로그래머스 - 타겟넘버

solution

나는 아래와 같은 과정을 통해 문제를 해결했다.

• 배열 인덱스를 하나씩 증가시키면서 bfs 진행
  • numbers[i] 을 더한경우와 뺀경우로 나누어서 진행

answer

#프로그래머스 - 타겟넘버 / 문제 유형 : bfs / Level 2
#(https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3)
#solution
#   - 배열 인덱스를 하나씩 증가시키면서 재귀 진행
#   - numbers[i] 을 더한경우와 뺀경우로 나누어서 진행

def bfs(numbers, num, i , answer,total,target):
    total += num

    if i == len(numbers)-1:
        if total == target:
            return answer + 1
                
    else:
        answer = bfs(numbers, numbers[i+1],i+1,answer,total,target)
        answer = bfs(numbers, -numbers[i+1],i+1, answer,total,target)
        
    return answer


def solution(numbers, target):
    answer = 0
    i = 0
    answer += bfs(numbers, numbers[i], 0, 0,0, target)
    answer += bfs(numbers, -numbers[i], 0, 0,0, target)
    
    return answer

 

추후에 생각난 방법이라 추가한다. 아래 방법이 bfs에 더 가깝고 간단할 듯 하다.

from collections import deque


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

    q = deque()
    q.append([-1 * numbers[0], 0])
    q.append([numbers[0], 0])

    while q:
        res, index = q.popleft()
        index += 1
        if index < length:
            q.append([res + numbers[index], index])
            q.append([res - numbers[index], index])
        else:
            if target == res:
                answer += 1

    return answer

 

질문이나 궁금하신점 또는 제가 잘못 알고있는 정보는 댓글 부탁드립니다😊