[프로그래머스] 타겟 넘버 (LV2 - JavaScript)

프로그래머스

1. 문제

 

제한사항

입출력 예

입출력 예 설명

 

2. 정답 풀이

풀이 전략

• 모든 연산자의 케이스를 담는 연산자 배열을 만든다.
• 연산자 배열을 순회하며 연산을 수행한다.
• 연산의 결과가 target과 같으면 answer를 증가시킨다.

function solution(numbers, target) {
    let answer = 0;
    const len = numbers.length;

    for (let i = 0; i < 2 ** len; i++) {
        const operators = []; // 연산자 배열
        let num = 0; // 연산의 결과를 할당할 변수
        for (let j = 0; j < len; j++) {
            // & 연산은 모두 1일 때만 1 => + 리턴
            operators.push((i & (1 << j)) ? '+' : '-');
        }
        // 연산자 배열 순회하며 연산의 결과가 target과 같으면 answer++
        operators.forEach((operator, idx) => {
            num = operator === '+' ? num + numbers[idx] : num - numbers[idx];
        })
        if (num === target) answer++;
    }
    
    return answer;
}

 

카테고리가 깊이/너비 우선탐색(DFS/BFS)인건 알지만, 로직이 생각나지 않아서 일단 편법으로 연산자 배열 생성해서 풀어봤다. 

통과는 했지만, 시간 복잡도가 O(2^n * n)이다. 여기서 n은 입력 numbers 배열의 길이(length)다.

1번 2번 테스트 케이스만 봐도 시간이 오래 걸리니까 numbers의 길이가 길어지면 메모리 overflow가 발생할 것 같다..😂

문제 취지에 맞게 재귀 함수로 다시 풀어야 겠다.

 

3. 최종 풀이

풀이 전략

• 재귀 함수 사용

function solution(numbers, target) {
    let answer = 0;
   
    // idx : 현재 인덱스
    // value : 현재까지 연산 결과
    const operate = (idx, value) => {
        if (idx < numbers.length) {
        	// 재귀적으로 +, - 연산 호출
            operate(idx+1, value + numbers[idx]);
            operate(idx+1, value - numbers[idx]);
        } else answer += value === target ? 1 : 0; // 연산 결과가 target과 같으면 answer++;
    }
    
    operate(0, 0);
    return answer;
}

 

 

실행 시간이 차이가 어마어마하다. 생각이 안 나서 편법으로 풀었는데, 결국엔 이런 방법이 성능 문제를 일으킨다는 걸 알게 됐다. 앞으로는 편법 사용하지 않고,  정공법으로 착실하게 문제를 풀어야겠다😂😂

 

 

[프로그래머스] 뉴스 클러스터링(2018 Kakao Blind Recruitment) (LV2 - JavaScript)

 

[프로그래머스] 전화번호 목록 (LV2 - JavaScript)