프로그래머스 타겟넘버

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

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

 

#include <string>
#include <vector>
#include <queue>
#include<iostream>
#include<string>
#include<map>
using namespace std;
int ret = 0;//최종값
int d[21] = { 0 };
void dfs(int idx,int target,vector<int>numbers) {
	if (idx == numbers.size()) {

		int num = 0;
		for (int i = 0; i < numbers.size();i++) {
			num += numbers[i] * d[i];
		}
		if (num == target) ret++;
		return;
	}
	d[idx] = 1;
	dfs(idx + 1, target, numbers);
	d[idx] = -1;
	dfs(idx + 1, target, numbers);	

}
int solution(vector<int> numbers, int target) {
	int answer = 0;
	dfs(0, target, numbers);
	return answer=ret;
}
int main(void) {
	cout << solution({ 1,1,1,1,1 }, 3);
	return 0;
}

오랜만에 구현력을 키우기 위해 문제를 풀어보았다. 

처음에 이문제는 구현을 할때 모든 경우를 다뽑아서 진행을 했다. n의 값이 20 이고 순열로 값을 뽑기때문에 시간초과의 걱정을 햇다 하지만 이렇게 구현을 해도 통과는 한다. 그래도 원래 최적화가 중요하다고 생각한다. 

 

그래서 이문제는 좀더 빠르게 문제를 풀어 보았다. 

몇개의 실행 결과 시간을 가져와봤다. 1번 테스트 부터 느릿느릿한것으로 봐서 무조건 최적화 각인것 같다.

 

#include <string>
#include <vector>
#include <queue>
#include<iostream>
using namespace std;
int ret = 0;//최종값
int d[21] = { 0 };
void dfs(int idx, int &target,int sum, vector<int>&numbers) {
	if (idx == numbers.size()) {
		if (sum == target) ret++;
		return;
	}
	dfs(idx + 1, target,sum + numbers[idx],numbers);
	dfs(idx + 1, target, sum - numbers[idx],numbers);

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

	return answer = ret;
}

이렇게 구현했다 따로 계산하는것이 아니고 계산하면서 dfs를 타고타고 들어가는 방식으로 구현하면

더빨라진다고 자부할 수 있다. 

속도는 얼마나 빨라졌나 보겠다.

차이가 보이나 그냥 애초 부터 이렇게 짜야한다는것을 보여준다. 앞으로 나도 이렇게 처음부터 구현해야겠다.

항상 문제 풀기에만 급급하다보니 이러는내가 한심하지만 이렇게 풀수 있는 능력이 있으니 항상 차분히 문제를 풀자.