(Week3)[BFS] 타겟넘버

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 15분  (풀었던 문제)

1. 문제 설명

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

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

사용할 수 있는 숫자가 담긴 배열에서 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟넘버 만들기

2. 접근 방식

• 숫자에 대해 할 수 있는 것은 더하거나 빼는 두 가지 경우인데, 이를 재귀나 이렇게 풀게 되면 2의 제곱으로 커짐
• 따라서 BFS의 방법으로 문제를 풀어야 한다. (별도의 리스트를 만들어서 모든 변화 과정을 기록하기)
• 코드가 진행될 수록 2의 제곱으로 경우의 수가 생성됨.

3. 코드

def solution(numbers, target):
    answers = [0]
    for i in numbers:
        tmp = []
        for j in answers:
            tmp.append(j+i)
            tmp.append(j-i)
        answers = tmp
    return answers.count(target)

n = [1, 1, 1, 1, 1]
t = 3
출력
# answers [0]
# tmp [1, -1]
# answers [1, -1]
# tmp [2, 0, 0, -2]
# answers [2, 0, 0, -2]
# tmp [3, 1, 1, -1, 1, -1, -1, -3]
# answers [3, 1, 1, -1, 1, -1, -1, -3]
# tmp [4, 2, 2, 0, 2, 0, 0, -2, 2, 0, 0, -2, 0, -2, -2, -4]
# answers [4, 2, 2, 0, 2, 0, 0, -2, 2, 0, 0, -2, 0, -2, -2, -4]
# tmp [5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5]

4. 코멘트

• 이전에 풀었던 문제였기 때문에 비교적 빠르게 아이디어를 얻어 풀 수 있었다.
• 그런데 아마 이전에 다른 해설을 보고 풀었던 것으로 기억하는데, 뭐 어쨌든 지금은 안 보고 풀 수 있으니까...