[프로그래머스] 타겟 넘버

풀이

1. bfs

function solution(numbers, target) {
    var answer = 0;
    let q = [];
    q.push([0,0]); //value,index
    while (q.length!==0) {
        let value = q.shift(); // value[0] : 누적값,value[1]:index
        // 현재 위치가 숫자의 최종길이와 같으면(사용 가능한 숫자 모두 사용)
        if (value[1]===numbers.length){
            if (value[0]===target) {
                answer +=1
            }
        } else {
            q.push([value[0]+numbers[value[1]],value[1]+1]);
            q.push([value[0]-numbers[value[1]],value[1]+1]);
        }
    }
    return answer;
}

• 테스트케이스 1,2 번 시간초과 발생

해결코드

function solution(numbers, target) {
    var answer = 0;
    function bfs (startIdx,numbers,target){
        const queue = [];
        queue.push([numbers[startIdx],-numbers[startIdx]]); //value,index
        let idx = startIdx+1;
        
        while (queue.length!==0) {
            let value = queue.shift();
            if (idx===numbers.length){
                for (let num of value) {
                    if (num===target) {
                        answer++;
                    }
                }
            } else {
                // 아직 마지막까지 모든 숫자를 사용하지 않았다.
                let tmpList = [];
                for (let num of value) {
                    tmpList.push(num+numbers[idx]);
                    tmpList.push(num-numbers[idx]);
                }
                idx++;
                queue.push(tmpList)
            }
        }
        return answer
    }
    answer= bfs(0,numbers,target)
    return answer;
}

• 프로그래머스 질문하기에 남겨져있는 bfs문제를 통해 학습하고 기존코드에 적용시켜 보았다.
• 그 결과 시간초과가 발생하는 이유는 형태는 bfs인데 최악의 경우 dfs와 크게 다른 점이 사라지는 코드였다. 만약 노드가 적게 밑으로 나누어진다면 통과하지만 많아진다면 조금 낳은 dfs와 같은 느낌의 코드였다.
• tmpList에 같은 너비에 해당하는 모든 노드를 push해준 후 idx에 값을 더해준다.

flatMap()

//너비 우선 방식 BFS
function solution(numbers, target) {
    const result = numbers.reduce((all, n) => all.flatMap(v => [v+n, v-n]), [0]);
    return result.filter(r => r === target).length;
}

flatMap() 이란?

정의 : 먼저 매핑함수를 사용해 각 엘리먼트에 대해 map 수행 후, 결과를 새로운 배열로 평탄화

let arr1 = [1, 2, 3, 4];

arr1.map(x => [x * 2]);
// [[2], [4], [6], [8]]

arr1.flatMap(x => [x * 2]);
// [2, 4, 6, 8]

• reduce()를 통해 배열을 누산하고 누산되 배열을 flatMap()을 통해 배열의 값들을 +,- 진행한다.
• initalValue 인 [0]에서 시작
  [1,-1] ->[2,0,0,-2]->[3,1,1,-1,1,-1,-1,-3] -> ... 이렇게 너비탐색으 진행할수 있다.
• result는 [ 5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5 ] 와 같은 결과가 값이 나온다. 노드를 보게되면 제일 하단의 노드 값들을 모두 얻을 수 있다.
• filter()를 통해 target과 같은 값들만 모아놓으 배열을 길이를 반환하면 된다.

2. dfs

function solution(numbers, target) {
    var answer = 0;
    //dfs
    function dfs(value,idx) {
        if (idx===numbers.length) {
            if (value ===target) {
                answer+=1
                return
            }
        }
        else {
            dfs(value+numbers[idx],idx+1)
            dfs(value-numbers[idx],idx+1)
        }
    }
    dfs(0,0)
    return answer;
}