매일매일 알고리즘 연습(5) - 타겟 넘버

주말에도 어김없이 고

알고리즘 문제 링크

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

문제

타겟 넘버

문제 설명
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
[1, 1, 1, 1, 1]
target
3
return
5

해결코드

function solution(numbers, target) {    
    // 제시된 값의 처음 양수, 음수 값을 초기값으로 설정
    // 해당 배열에는 더하거나 빼서 나올 수 있는 모든 경우의 수를 담는 배열
    let resList = [numbers[0], -numbers[0]];
    
    // 초기값은 설정됐으니, 다음 값부터 loop를 돌면서 로직 시작
    for(let i=1;i<numbers.length;i++){
        const tempList = [];
        
        // numbers에서 i번째까지의 숫자들이 서로 더하거나 빼서 나올 수 있는 모든 수를 담고 있는 배열을 돌면서 
        // 이번 값을 더하고 뺀 값들을 다시 배열에 넣어준다.
        for(let j=0;j<resList.length;j++){
            tempList.push(resList[j] + numbers[i], resList[j] - numbers[i]);
        }
        resList = tempList;
    }
    
    // 나올 수 있는 모든 수를 가지고 있는 배열중에 target과 같은 값을 가진 인자의 수를 반환
    return resList.filter(value => target === value).length;
}

추가설명

트리 구조를 생각하면서 시작

어렵거나 혼동되는 코드가 없으니 추가 설명은 없을 것 같고, 원리만 살짝 예를 들어 설명을 해보자면

[1,2,3,4,5] 라는 값이 주어진 경우에

처음 1로 만들 수 있는 값은 [1, -1] 이다.

그 다음 기존에 만들어진 [1, -1] 에서 2로 만들어 질 수 있는 값은

[1 + (2), 1 + (-2), -1 + (2), -1 + (-2)] --> [3, -1, 1, -3] 이다

그 다음 기존에 만들어진 [3, -1, 1, -3] 에서 3으로 만들어 질 수 있는 값은

[3 + (3), 3 + (-3), -1 + (3), -1 + (-3),
1 + (3), 1 + (-3), -3 + (3), -3 + (-3),] --> [6, 0, 2, -4, 4, -2, 0, -6] 이다

위와 같은 방식으로 진행하면, 마지막에 더하기/뺄셈으로 만들 수 있는 모든 경우의 수가 담긴 배열을 만들 수 있고, 해당 배열에서 원하는 target이 몇 개 있는 지 찾으면 해결할 수 있다.

잡담

이번 건 굉장히 금방 해결했다. (매일매일 알고리즘 연습의 효과!? 는 아니고, 사실 쉬운 알고리즘문제)

종이에 끄적끄적해보니 자연스럽게 트리구조가 나왔고, 코드로 작성하니 끝!난 알고리즘이였다.

중간에 시간 단축이나 최적화 작업을 들어갈 필요도 없었고,

이미 완성된 알고리즘들과 시간을 비교해봐도 별 차이가 없어서 비교 코드를 올리지 않았다.
(테스트케이스 1,2는 내가 더 느리지만, 나머지는 내가 더 빠르게 나왔다.)

오늘건 난이도가 낮다고 느꼈는데, 일주일정도 쉬운 난이도로 머리를 조금만 더 말랑하게 만들고 일주일 뒤부터는 난이도를 올려서 풀어봐야겠다.