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

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

1. 문제

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. 제한사항

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

3. 풀이

• BFS로 모든 경우를 다 구했다.
• (값, 인덱스) 쌍을 queue에 넣고 인덱스가 배열의 사이즈와 같을 때(=끝까지 다 계산했을 때) target 값과 같으면 answer를 증가시켰다.

4. 처음 코드와 달라진 점

• 처음에 큐에 첫 숫자를 양수와 음수로 넣어야 하는데 양수와 양수를 넣었다.

+21.08.31 추가

• 나중에 다시 문제를 풀었다.
• 큐를 값 인덱스 쌍으로 만들지 않는 방식으로 풀었는데 뭐가 더 낫다고 말을 못하겠다.

5. 풀이 2

• 똑같이 BFS로 모든 경우를 다 구한다.
• 큐에 입력되는 값을 계산된 값이 아니라 더할 지 뺄 지 경우를 넣어주었다.
  • vector가 들어가는 큐를 만든다.
  • vector에는 1과 -1을 넣는다.
• vector의 크기와 numbers의 크기가 같다면 계산을 해준다.
  • for-loop로 vector[i] * numbers[i]를 합계에 더해주면 된다.
  • vector에는 1과 -1이 들어있기 때문에 numbers의 각 값을 더하거나 빼는 것과 같은 효과가 난다.
• 계산 값이 target과 같다면 answer 값을 증가시켜준다.
• 다 풀고 나니 그 전 풀이가 나은 것 같기도 하다.

DFS로 풀어봐야겠다.

6. 코드 1

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    queue<pair<int, int>> q;
    q.push({numbers[0], 1});
    q.push({-numbers[0], 1});
    
    while(!q.empty()){
        int value = q.front().first;
        int index = q.front().second;
        q.pop();
        
        if(index == numbers.size()){
            if(value == target) answer++;
        }
        else{
            q.push({value+numbers[index], index+1});
            q.push({value-numbers[index], index+1}); 
        }
    }
    return answer;
}

7. 풀이 2 (+21.08.31)

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    queue<vector<int>> q;
    q.push({1});
    q.push({-1});
    
    while(!q.empty()) {
        vector<int> temp = q.front();
        q.pop();
        if (temp.size() == numbers.size()) {
            int sum = 0;
            for (int i = 0; i < temp.size(); ++i) {
                sum += numbers[i] * temp[i];
            }
            if (sum == target) answer++;
        }
        else {
            temp.push_back(1);
            q.push(temp);
            
            temp.pop_back();
            temp.push_back(-1);
            q.push(temp);
        }
    }
    return answer;
}

8.풀이(JS)

function solution(numbers, target) {
    let answer = 0;
    
    function dfs(L, sum) {
        if (L === numbers.length) {
            answer += sum === target ? 1 : 0;
        }
        else {
            dfs(L + 1, sum + numbers[L]);
            dfs(L + 1, sum - numbers[L]);
        }
    }
    
    dfs(0, 0);
    return answer;
}