[programmers] 타겟 넘버

코딩 테스트 연습 - 깊이/너비 우선 탐색(DFS/BFS)

---

<타겟 넘버>

문제 설명

 

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 이하인 자연수입니다.

 

문제 풀이

  - my solution

def solution(numbers, target):
    answer = 0
    
    root=[0] #처음 0부터 시작
    
    for i in numbers: #numbers에서 숫자를 받아와 root값에 더해주고 빼주는 경우의 수 
        temp=[]
        for j in root:
            temp.append(j+i)
            temp.append(j-i)
            root=temp #temp값을 root로 만들어줌
    
    answer=temp.count(target) #최종 결과 값에서 원하는 target 값이 몇개 있는지 확인
    
    return answer

1) root를 0 하나 두도록 설정

2) numbers의 숫자를 하나 받아와 root와 함께 계산해줘야 함

   2-1) 새로운 리스트 선언

   2-2) root의 값과 계산한 후 리스트에 넣고 root에 대입

3) temp리스트에 원하는 값이 몇 개 있는지 확인

---

생각🤔

 

처음에 깊이/너비 우선 탐색 문제라고 해서 겁부터 먹었던 문제이다.

사실 예전부터 몇번이나 이 문제를 봤지만 모르는 척 넘기기😥

이번에 한번 풀어보자 해서 봤지만 잘 모르게써요..😕 결국 검색의 힘을 조금 빌렸다😵

설명을 봤는데 아니, 이게 이렇게 쉬운 문제였다구?🤨

---

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges