프로그래머스 - 타겟 넘버(DFS/BFS) C++

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

내 풀이(BFS)

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    queue<int> sumQueue;
    sumQueue.push(numbers[0]);
    sumQueue.push(numbers[0] * -1);
    for(int i = 1; i<numbers.size(); ++i)
    {
        int currentNum = numbers[i];
        
        int quesize = sumQueue.size();
        for(int j =0; j<quesize; ++j)
        {
            int beforesum = sumQueue.front();
            sumQueue.pop();
            sumQueue.push(beforesum + currentNum);
            sumQueue.push(beforesum - currentNum);
        }
    }
    while(sumQueue.empty() == false)
    {
        if(sumQueue.front() == target)
        {
            answer++;
        }
        sumQueue.pop();
    };
  
    
    return answer;
}

 

타인의 풀이 1 - DFS 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int total = 0;
void DFS(vector<int>& numbers, int& target, int sum/*지금까지의 합*/, int n/*현재 깊이*/)
{
	//최종 깊이에 도달했을 때 - 탈출조건
	if (n >= numbers.size())
	{
		if (sum == target)
		{
			total++;
		}
		return;
	}
	

	DFS(numbers, target, sum + numbers[n], n + 1);
	DFS(numbers, target, sum - numbers[n], n + 1);
}

int solution(vector<int> numbers, int target)
{
	int answer = 0;
	DFS(numbers, target, numbers[0], 1);
	DFS(numbers, target, -numbers[0], 1);

	answer = total;
	return answer;
}

 

타인의 풀이 2 - 비트연산자 (최고다)

 

#include <vector>
#include <string>
using namespace std;

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

	for (int i = 0; i < size; i++)
	{
		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;
}