Programmers 43165. 타겟 넘버

Title

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
BFS/DFS	lv.2	30분	✅

설계 방법

숫자 배열과 타겟을 bfs 함수에 그대로 넘기고, 그 결과를 리턴한다.
bfs 함수는, 받은 숫자 배열의 복사본을 만들고 (pop 연산이 참조한 array를 모두변경하기 때문에)
복사본에서 마지막 숫자를 제거하고,
마지막 숫자가 제거된 배열과 마지막 숫자를 타겟 넘버에 +, - 연산을 한 결과를 타겟 넘버로 bfs 함수에 각각 보내고 결과를 리턴 받는다.
bfs 함수는 숫자 배열의 길이가 1일 때, 남은 숫자가 타겟 넘버 또는 - 타겟 넘버와같다면 1을 리턴한다.

코드

1차 풀이

javascript

function solution(numbers, target) {
	return bfs(numbers, target);
}

function bfs(numbers, target) {
	const clone = [...numbers];

	if (clone.length === 1) {
		return Number(clone[0] === target || clone[0] === -target);
	}

	const lastNumber = clone.pop();

	return bfs(clone, target - lastNumber) + bfs(clone, target + lastNumber);
}

function solution(numbers, target) {
	return bfs(numbers, target);
}

function bfs(numbers, target) {
	const clone = [...numbers];

	if (clone.length === 1) {
		return Number(clone[0] === target || clone[0] === -target);
	}

	const lastNumber = clone.pop();

	return bfs(clone, target - lastNumber) + bfs(clone, target + lastNumber);
}

2차 풀이

☝ 다시 보니 이건 먼저 실행하는 함수부터 깊이 우선 탐색하기 때문에 dfs 였다. 그리고 numbers.length === 0 일 때 까지 반복하는 것이 코드 가독성이 높았다. 배열은 참조형이기 때문에 매개변수로 받은 배열을 pop 하면 원본 배열도 변하므로복사본을 넘겨주었다.

javascript

function solution(numbers, target) {
	return dfs(numbers, target);
}

function dfs(numbers, target) {
	if (!numbers.length) {
		return target === 0 ? 1 : 0;
	}

	const lastNumber = numbers.pop();

	return (
		dfs([...numbers], target - lastNumber) +
		dfs([...numbers], target + lastNumber)
	);
}

function solution(numbers, target) {
	return dfs(numbers, target);
}

function dfs(numbers, target) {
	if (!numbers.length) {
		return target === 0 ? 1 : 0;
	}

	const lastNumber = numbers.pop();

	return (
		dfs([...numbers], target - lastNumber) +
		dfs([...numbers], target + lastNumber)
	);
}

Programmers 43165. 타겟 넘버

설계 방법

코드

시간 복잡도

어려웠던 점

참고자료

Programmers 43165. 타겟 넘버

설계 방법 #

코드 #

시간 복잡도 #

어려웠던 점 #

참고자료 #

설계 방법

코드

시간 복잡도

어려웠던 점

참고자료