펜잡이 개발자>[알고리즘_DFS]프로그래머스 "타겟 넘버" 문제 풀이

---

데브림의 블로그 포스팅 한 것들을 한 눈에 확인하고 싶다면 클릭!

👉 https://github.com/DevLimK1/tistory-map 👈 

---

🤔포스팅을 통해 얻어갈 수 있는 지식🧐

✔ DFS를 활용한 문제 풀이 방법

---

 

(문제 사이트 이동)

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

문제 설명

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

---

문제 접근

문제에 주어진 1,1,1,1,1 이 너무 범위가 커서 1,1,1 3개로 범위를 좁혀서 문제를 접근했다.

예시)

numbers:{1,1,1}

target:1 로 주어질 때

numbers에 있는 수인 1,1,1로 더하고 빼서 target인 1을 만들 수 있는 모든 경우의 수를 합한 것이 정답이다.

• 1+1+1=3
• 1+1-1=1 ✔
• 1-1+1=1 ✔
• 1-1-1=-1
• -1+1+1=1 ✔
• -1+1-1=-1
• -1-1+1=-1
• -1-1-1=-3

⇒ 총 3이 정답!

 

😀 메서드를 호출 할 때 순서를 그려보았습니다.
아래로 길게 그렸기 때문에 중간에 그림이 짤렸는데 이어서 보기에는 크게 지장이 없는 거 같아서 양해바랍니다ㅠㅠ

재귀함수를 사용하다보니 머릿속으로 그림이 잘 그려지지 않아서 직접 그려보았는데
이 글을 읽는 분들 중에 필자 처럼 머릿속에 그림이 그려지지 않으시면 한번 그려보시면 이해하는데 수월할 겁니다 : )

검정색 번호 순서대로 메서드 호출을 타고 들어간다고 보면 됩니다. 빨간색 화살표시와 숫자는 return 할 때 값 입니다.(구체적인 메서드 식은 아래 소스코드 참고)

소스 코드

1: public class 타겟넘버 {
   2:     public int solution(int[] numbers, int target) {
   3:         return DFS(numbers, target, 0, 0);
   4:     }
   5: 
   6:     public int DFS(int[] numbers, int target, int index, int num) {
   7:         if (index == numbers.length) {
   8:             return num == target ? 1 : 0;
   9:         } else {
  10:             int firstDFS = DFS(numbers, target, index + 1, num + numbers[index]);
  11:             int secondDFS = DFS(numbers, target, index + 1, num - numbers[index]);
  12:             return firstDFS + secondDFS;
  13:             
  14:             // firstDFS+secondDFS 를 아래처럼 리팩토링 가능
  15:             //  return DFS(numbers, target, index + 1, num + numbers[index] 
  16:             //  + DFS(numbers, target, index + 1, num - numbers[index]);
  17:         }
  18:     }
  19: }

😀 코드가 잘 이해가 안간다면, 디버깅 해보면서 천천히 흐름을 따라가 보는 것을 추천합니다!

---

긴 글 끝까지 읽어주셔서 감사합니다 : )

포스팅은 스스로 습득한 지식과

강의, 블로그, 서적 등을 참고해서 이해한 것을 바탕으로 정보를 공유합니다. 

포스팅에 문제가 있거나, 수정이 필요한 부분 , 질문이 있으시면 댓글 남겨주세요.

도움이 되셨다면 공감(♥)버튼, 댓글은 작성자에게 큰 힘이 됩니다.