43165. 타겟 넘버

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

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

설계 방법

• 숫자 배열과 타겟을 bfs 함수에 그대로 넘기고, 그 결과를 리턴한다.

• bfs 함수는, 받은 숫자 배열의 복사본을 만들고 (pop 연산이 참조한 array를 모두변경하기 때문에)

• 복사본에서 마지막 숫자를 제거하고,

• 마지막 숫자가 제거된 배열과 마지막 숫자를 타겟 넘버에 +, - 연산을 한 결과를 타겟 넘버로 bfs 함수에 각각 보내고 결과를 리턴 받는다.

• bfs 함수는 숫자 배열의 길이가 1일 때, 남은 숫자가 타겟 넘버 또는 - 타겟 넘버와같다면 1을 리턴한다.

코드

• 1차 풀이

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 하면 원본 배열도 변하므로복사본을 넘겨주었다.

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)    );}

시간 복잡도

• O(2^N)

어려웠던 점

• bfs 문제가 처음이어서 방법을 떠올리는 것이 쉽지 않았다.

• 테스트 케이스가 1개여서 힘들었다.

참고자료