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

문제 정보

제목 : 타겟 넘버

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

 

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4 +1 -2+1 = 4
+4 -1+2 -1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

---

나의 풀이

탐색 관련하여 공부를 했지만 문제를 푸는 건 아직 익숙하지 않아 활용하기 힘들었습니다. stack에 초기값으로 (0,0)을 저장해 줍니다. while문을 이용하여 stack에 요소가 남아있는 동안 반복하면서 index, num에 stack을 pop()하여 저장합니다. 만약 index와 numbers의 길이가 일치하면 num과 target을 비교하여 일치하면 answer에 +1을 하고 continue 해줍니다. 아니라면 stack에 index+1 한 값과 numbers [index]를 더한 값과 뺀 값, 이 두 가지 경우를 전부 저장하여 반복합니다. stack이 비게 된다면 answer을 리턴합니다.

탐색 관련한 문제를 조금 더 빨리 풀 수 있도록 익혀야 할 것 같습니다.

 

코드

def solution(numbers, target):
    answer = 0
    stack = [(0,0)]
    
    while (stack) :
        index,num = stack.pop()
        
        if index == len(numbers):
            if num == target :
                answer +=1
            continue
        
        stack.append((index+1, num + numbers[index]))
        stack.append((index+1, num - numbers[index]))
    return answer