[c++] 프로그래머스 :: 타겟넘버 (brute force, 문제 풀이, 코드)

타겟 넘버

문제

https://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

---

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int bruteForce(int num, vector<int>& numbers, int target){
    // num : +의 갯수
    int size = numbers.size();
    int answer = 0;
    vector<int> tmp(size, -1); // tmp는 1과 -1만 존재하는 배열
    for(int i=0; i<num; i++){
        tmp[size-1-i]=1; // -1이 1보다 먼저 와야 next_permutation이 동작함
    }
    do{
        int sum=0;
        for(int i=0; i<size; i++){
            sum+= numbers[i]*tmp[i];
        }
        if(sum==target)
            answer++;
    }while(next_permutation(tmp.begin(),tmp.end()));
    return answer;
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = numbers.size();
    sort(numbers.begin(), numbers.end());

    vector<int> range;

    for(int i=1; i<=size; i++){ // +의 갯수
        int max =0; int min =0;
        for(int j=0; j<i; j++){ 
            max += numbers[size-1-j]; // sort되어있으므로 가장 큰 수부터 + 주기
            min += numbers[j]; // sort되어있으므로 가장 작은 수부터 + 주기
        }
        for(int j=i; j<numbers.size(); j++){ // 나머지는 -
            max -= numbers[size-1-j];
            min -= numbers[j];
        }
        if(target>=min && target<=max)
            range.push_back(i); // target number가 범위 안에 속하면 후보에 넣기
    }

    for(int i=0; i<range.size(); i++)
        answer += bruteForce(range[i], numbers, target);

    return answer;
}

 

풀이

 처음에는 모든 숫자를 줄 세운 후에 +, -를 끼워넣거나, 모든 숫자의 +, - 한 수들을 줄 세우거나 하는 brute force 방법을 생각했다. 하지만 숫자의 갯수가 20개까지도 될 수 있으므로 brute force를 쓴다면 2^20의 경우의 수를 감당해야했다. brute force를 사용하면서 검사하는 범위를 줄이면 괜찮지 않을까?

 본인은 +의 갯수로 경우를 나누기로 했다. +가 n개일 때 나올 수 있는 최대, 최소값을 구한 후 target 숫자가 그 범위 안에 속한다면 해당 +의 갯수를 조사하기로 한 것이다.

 따라서 처음에 나온 for문에서 후보가 되는 +의 갯수를 조사하였다. 여기서는 size만큼 반복하면서 내부 반복문에서 또 size만큼 반복하기 때문에 20^2=400 의 시간복잡도가 필요하다.

 그 후에 후보인 수들을 넘겨서 순열로 조사하면서 target 숫자를 만들 수 있는 방법이 있는지를 bruteForce 함수로 계산하였다. 우선 tmp라는 numbers와 사이즈가 같은 배열을 모두 -1로 초기화해준 다음, 넘겨받은 +의 갯수만큼 뒤에서부터 1로 채워준다.

처음에 여기에서 실수를 해서 [1,1,1,1,-1] 과 같은 식으로 1을 먼저 채워줬는데, 이렇게 진행하면 next_permutation 함수가 돌지 않는다.

[-1,1,1,1,1] 과 같이 오름차순으로 적어줘야한다.

 그리고 tmp 배열의 순열에 따라 numbers에 곱해준 다음 더해서 target 숫자와 일치하는지 확인하면 된다.

 

채점 결과

다른 사람의 풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = 1 << numbers.size();

    for(int i = 1 ; i < size ; i++){ //2^20
        // 1부터 쭉 조사
        // 1, 10, 11, 100, ...
        // 1이 있는 index가 -인 number

        int temp = 0;
        for(int j = 0 ; j < numbers.size() ; j++)
        {  
            if(i &(1 << j)){
                temp -= numbers[j];
            }
            else temp += numbers[j];
        }
        if(temp == target) answer++;
    }
    return answer;
}

bit mask로 문제를 해결했다. 똑똑쓰.