[프로그래머스] 깊이/너비 우선 탐색 - 타겟 넘버 문제 풀이

오늘은 프로그래머스에서 처음 다룰 깊이/너비 우선 탐색(DFS/BFS) 문제 중 타겟 넘버 문제 풀이를 해보겠습니다. 이 문제의 포인트는 깊이/너비 우선 탐색(DFS/BFS) 알고리즘을 활용하여 문제를 풀이하는 것입니다. 그럼 타겟 넘버 문제 풀이 시작해보겠습니다.

 

 

프로그래머스 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버 문제 풀이

 

 

 

 

♥ 문제 정보

• 문제명: 타겟 넘버
• 문제 난이도: Level 2
• 문제 푼 사람 수: 32342명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

♥ 문제 설명

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 함수를 작성해주세요.

 

 

이 문제는 수 리스트를 통해 연산의 결과가 타겟 넘버와 같은 경우의 수를 반환하는 문제입니다. 

• 사용할 수 있는 숫자의 리스트로 +/-를 통해 타겟 넘버를 만들 수 있는 경우의 수 구하기
• Inputs
  • numbers: 연산에 사용할 수 있는 숫자 리스트
  • target: 리스트에 있는 숫자들의 연산을 통해 만들어야하는 숫자
• Output: numbers의 숫자들의 +/- 연산을 통해 target 값을 만들 수 있는 경우의 수

 

 

 

 

♥ 제한 사항

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

 

 

• 2 ≤ numbers의 개수(N) ≤ 20
• 1 ≤ 각 숫자의 값(자연수) ≤ 50 
• 1 ≤ target(자연수) ≤ 1,000

 

 

 

 

♥ 입출력 예

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

 

 

 

 

♥ 알고리즘 만들기

1. 모든 숫자 값에 대해서 순서대로 +/- 연산을 모두 수행하도록 한다.
2. 최종 숫자까지의 연산을 통해 target 값과 같으면 경우의 수를 증가한다.
3. 모든 숫자 리스트(numbers)의 +/- 연산을 수행하였을 때의 최종 경우의 수를 반환한다.

 

 

이 때, 1번의 모든 숫자 리스트에 대해서 순차적으로 +/- 연산을 수행하도록 하는 알고리즘을 숫자 리스트를 더 깊이 파고들면서 순차적으로 확인하는 DFS를 활용하여 구현하겠습니다.

 

 

 

 

♥ 코드 구현

function solution(numbers, target) {
    var answer = 0;
    calculating(0, 0)

    function calculating(index, result) {
        // 2. 최종 숫자까지의 연산을 통해 target 값과 같으면 경우의 수를 증가한다.
        if(index == numbers.length - 1) {
            if(result + numbers[index] == target) {
                answer++;
            }
            if(result - numbers[index] == target) {
                answer++;
            }
            return;
        }
        
        // 1. 모든 숫자 값에 대해서 순서대로 +/- 연산을 모두 수행하도록 한다.
        calculating(index+1, result + numbers[index]);
        calculating(index+1, result - numbers[index]);
    }
    
    // 3. 모든 숫자 리스트(numbers)의 +/- 연산을 수행하였을 때의 최종 경우의 수를 반환한다.
    return answer;
}

 

 

알고리즘은 비교적 간단하게 만들었지만, 해당 내용을 구현함에 있어 재귀함수를 통한 DFS를 활용하여 구현하였습니다. calculating() 함수를 계속 호출함에 따라 점점 index가 증가하며, numbers의 최종 숫자로 이동하는 과정을 확인할 수 있습니다.

 

 

 

 

♥ 채점 결과

 

 

제한사항에서 N의 최대 값이 50이었던 점을 미루어봤을 때, 효율성 테스트 케이스는 없을 것으로 예상하였습니다.

이에, 정확성 테스트 케이스만 8개가 있으며, 모두 통과하여 100점으로 타겟 넘버 문제 풀이를 마치겠습니다.