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

[프로그래머스] 타겟 넘버 링크

전체 코드는 다음과 같다

def solution(numbers, target):
    answer = 0
    result = [0]
    for number in numbers:
        temp_sum = []
        for res in result:
            temp_sum.append(res + number)
            temp_sum.append(res - number)
        result = temp_sum

    for i in result:
        if i == target: answer += 1

    print(answer)
    return answer

✅ Input

• numbers: 사용할 수 있는 숫자가 담긴 배열
• target: numbers안에 배열의 수를 적절히 더하거나 빼서 도달하는 타겟 넘버

  입력을 numbers=[3 1 2 5 4], target=5 라고 가정 하면 조합의 모든 경우는 [-3 1 -2 5 4], [3 -1 2 5 -4], [3 1 2 -5 4] 이다.

  따라서 출력은 3이 나와야 한다.

---

✅ Process

🎯 알고리즘 설명

numbers = [ 3, 1, 2, 5, 4], target = 5 가정한다.

numbers의 원소마다 +, -를 붙여서
result 배열에 저장하기를 반복한다.

numbers = 3 👉 result = [+3, -3]
numbers = 1 👉 result = [+3+1, +3-1, -3+1, -3-1]
numbers = 2 👉 result = [+3+1+2,+3+1-2, +3-1+2,+3-1-2, -3+1+2,-3+1-2, -3-1+2,-3-1-2]

.........

numbers = 4 👉 result = 모든 BFS 경우의 합

해당 result 배열의 원소 중에서 target과 일치하는 원소가 있을때마다 answer에 +1을 해준다.

---

🎯 코드 설명

📘 연산 부분

    answer = 0
    result = [0]
    for number in numbers:
        temp_sum = []
        for res in result:
            temp_sum.append(res + number)
            temp_sum.append(res - number)
        result = temp_sum

• answer: 출력 결과가 저장될 변수

• result = [0]: 모든 조합의 합들이 저장될 배열, 초기값은 0이다.

• temp_sum=[]: 해당 배열은 number가 바뀔때마다 초기화

• temp_sum.append(res +/-number): numbers의 원소마다 +, -를 붙여서 result 배열에 저장

---

📘 출력 부분

  for i in result:
        if i == target: answer += 1

    print(answer)
    return answer

target과 일치하는 result의 원소가 존재하면 answer + 1 하고 answer을 출력한다.

---

✅ Output

🎯 예시에 대한 출력 결과

if __name__ == '__main__':
    solution([1, 1, 1, 1, 1], 3) #5
    solution([1, 1, 1, 1, 1, 1], 2) #15
    solution([3, 2, 1, 5, 4], 5) #3	

순서대로 5, 15, 3이 출력된다.

---

🎯 출력시간

테스트 1 〉	통과 (169.24ms, 50.1MB)
테스트 2 〉	통과 (185.00ms, 49.4MB)
테스트 3 〉	통과 (0.16ms, 10.2MB)
테스트 4 〉	통과 (0.81ms, 10.3MB)
테스트 5 〉	통과 (5.11ms, 11.2MB)
테스트 6 〉	통과 (0.33ms, 10.3MB)
테스트 7 〉	통과 (0.17ms, 10.2MB)
테스트 8 〉	통과 (1.26ms, 10.5MB)

---

🎯 다른 사람의 코드와 출력시간

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])

테스트 1 〉	통과 (366.10ms, 10.2MB)
테스트 2 〉	통과 (384.23ms, 10.2MB)
테스트 3 〉	통과 (0.57ms, 10.3MB)
테스트 4 〉	통과 (2.75ms, 10.2MB)
테스트 5 〉	통과 (19.72ms, 10.2MB)
테스트 6 〉	통과 (0.74ms, 10.2MB)
테스트 7 〉	통과 (0.59ms, 10.2MB)
테스트 8 〉	통과 (5.81ms, 10.2MB)

재귀호출의 방식을 사용했기 때문에 시간적인 면에서는 느리다. 하지만 재귀호출 방식에 대해 공부도 할 겸 코드를 분석해봤다.

---

🎯 다른 사람의 코드분석

return solution(numbers[1:], target-numbers[0])
+ solution(numbers[1:], target+numbers[0])

이 부분이 핵심이면서 내 코드와 유사한 점이라고 생각한다.
target에서 numbers의 첫 번째 원소만큼 빼고/더하면서 numbers = numbers[1:] 이 된다.

    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0

그러다 numbers가 마지막 원소까지 가게된다면,
해당 상태에서 target이 0 이면 answer +=1 아니라면
answer += 0이라고 할 수 있다.