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

문제

 

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

numbers     target     return

[1, 1, 1, 1, 1]

3

5

입출력 예 설명

문제에 나온 예와 같습니다.

---

해설

이 문제를 접했을 때, 생각했던 사고이다.

탐색(root) -> 빼기 -> 다음 탐색(cur) -> 빼기 -> sum <= target -> 이전 인덱스(root)로 이동, 다음 인덱스(cur++) 탐색 
sum == target일 경우 cnt++

 

이 문제는 깊이/너비 우선 탐색(DFS/BFS)에 속하는 문제인데, 이 부분에 있어 특히나 내가 약하기 때문에 문제를 푸는데 꽤 오랜 시간이 소요됐다. 특히나, 코드 23번 째 줄에서 sum += (numbers[root] * 2)를 numbers[cur]로 풀어서 계속 실패했었다. 생각해보니, cur은 한 계층에서 계속 증가하고, 결국엔 배열의 마지막 인덱스를 가리키니 의미가 없었던 것이다. 나름 이리저리 생각해서 해결하긴 했는데, 사실 어거지로 해결한 감이 없지는 않다. 

 

function solution(numbers, target) {
    var cnt = 0;
    var sum = numbers.reduce((a, b) => a + b);

    numbers.sort((a, b) => b - a);
    numbers.unshift(0); // 더미 헤드

    search(0, 0);

    function search(root, cur){
        // root는 상위 존재 cur은 같은 계층
        root = cur;
        sum -= (numbers[cur] * 2);
        if(sum <= target){
            if(sum == target) cnt++;
            sum += (numbers[cur] * 2);
            return;
        }
        while(cur < numbers.length - 1){
            cur++;
            search(root, cur);
        }
       sum += (numbers[root] * 2);
    }
    return cnt;
}

 

 

느낀 점

• 이제는 자료구조에 있어서 좀 더 제대로 공부해야할 필요가 있을 것 같다. 지금까지는 그저 정렬 문제의 성향이 강해서 해결이 가능했는데, 그래프 문제가 나오니 확실히 어렵다는 걸 느꼈다. (프로그래머스에서 이 문제를 해결했을 때 주는 점수는 1점이다..)
• 다른 사람의 풀이를 보니, 정말 간단하게 풀기는 했는데, 대부분 완전 탐색이었다. 이 문제의 의도와는 조금 다르지만 그래도, 짧은 코드로 완전 탐색이 가능하니 이 참에 내 것으로 만들도록 하자.

완전 탐색의 경우, 두 가지의 경우를 만들면 되는데, 하나는 합계에 현재의 값을 더하는 것이고, 나머지는 합계에 현재의 값을 빼하는 것이다. 그렇게 되면, 재귀를 통해서 모든 경우를 얻게 되는데, 이 중에서 합계가 target과 동일한 경우만 세면 된다.