[프로그래머스/JavaScript] 타겟 넘버 (Feat. forEach 함수)

 

📃 최종 코드

테스트 통과에 정말 많은 시간이 소요되었습니다. (왜인지 확인하기 위해 시간복잡도를 확인해 봤습니다.)

아래 코드에서 저는 먼저 numbers 배열의 합을 구한 뒤,
1부터 numbers 배열의 길이까지의 원소를 선택하는 모든 조합을 구합니다.
각 조합의 합이 목푯 값과 일치하는지 확인합니다.

이렇게 모든 조합을 구하는 과정에서 getCombine 함수를 사용하며,
이 함수는 numbers 배열의 각 원소를 기준으로 재귀적으로 조합을 구합니다.
따라서, 이 함수의 시간 복잡도는 O(2^n)입니다.

전체 코드의 시간 복잡도는
각 원소를 선택하는 경우의 수(2^n)와 원소를 선택하는 횟수(n)를 곱한 O(n * 2^n)

function solution(numbers, target) {
    let answer = 0;
    
    let sum = 0;
    for (let number of numbers) {
        sum += number; // 배열의 모든 숫자 합
    }
    
    let sumTarget = (sum - target) / 2; // 타겟 값 계산
    
    // 1개 이상의 원소를 선택하는 경우에 대해 반복
    for (let i = 1; i <= numbers.length; i++) {
        let combinations = getCombine(numbers, i); // 조합 생성
        
        combinations.forEach(combination => {
            let sum = combination.reduce((a, b) => a + b, 0); // 조합의 합 계산
            
            if(sumTarget === sum) {
                answer++; // 합이 타겟 값과 일치할 경우, 경우의 수 증가
            }
        })
    }
    
    return answer;
}

// 주어진 배열에서 선택할 수 있는 원소의 개수에 따른 모든 조합을 구하는 함수
function getCombine (arr, selectNum) {
    const result = [];
    
    // 선택 원소가 1개일 때, 배열로 반환
    if(selectNum === 1) {
        return arr.map((val) => [val]);
    }
    
    // 선택 원소가 1개 초과일 때
    arr.forEach((curVal, curIdx, arr) => {
    	// 현재 원소를 제외한 나머지 배열
        const restArr = arr.slice(curIdx + 1);
        // 재귀 호출로 조합 생성
        const combine = getCombine(restArr, selectNum - 1);
        // 현재 원소와 조합 결합
        const attached = combine.map((combo) => [curVal, ...combo]);
        
        // 결과에 추가
        result.push(...attached);
    });
    
    return result;
}

 

---

 

시간 복잡도를 줄이기 위해 최적화 코드는 DFS(깊이 우선 탐색)입니다.

DFS를 통해 numbers 배열의 모든 원소에 대해 더하거나 빼는 방법을 모두 탐색하는 것인데요.

 

아래 코드를 확인해 보겠습니다.

 

🌊 DFS를 사용한 코드

function solution(numbers, target) {
    let answer = 0;

    function dfs(index, sum) {
    	// 모든 숫자를 다 더하거나 뺐을 때 (탐색의 끝에 도달했을 때)
        if(index === numbers.length) {
        	// 현재의 합이 타겟 숫자와 같다면
            if(sum === target) {
                answer++;
            }
            return;
        }
        // 다음 숫자를 더하는 경우
        dfs(index + 1, sum + numbers[index]);
        // 다음 숫자를 빼는 경우
        dfs(index + 1, sum - numbers[index]);
    }
    
    // DFS 시작 (초기 인덱스 0, 초기 합계 0)
    dfs(0, 0);
    
    return answer;
}

<numbers가 [4, 1, 2, 1]이고 target이 4일 때, dfs 함수의 계산 단계>

1. dfs 함수를 처음 호출하면 index는 0, sum은 0입니다.
2. 첫 번째 숫자인 4를 더하는 경우와 빼는 경우를 각각 탐색합니다.
  - 더하는 경우: dfs(1, 4)
  - 빼는 경우: dfs(1, -4)
3. 더하는 경우인 dfs(1, 4)에서는 다음 숫자인 1을 더하는 경우와 빼는 경우를 각각 탐색합니다.
  - 더하는 경우: dfs(2, 5)
  - 빼는 경우: dfs(2, 3)
4. 빼는 경우인 dfs(1, -4)에서는 다음 숫자인 1을 더하는 경우와 빼는 경우를 각각 탐색합니다.
  - 더하는 경우: dfs(2, -3)
  - 빼는 경우: dfs(2, -5)
5. 이렇게 모든 숫자에 대해 더하거나 빼는 경우를 모두 탐색합니다.
6. 모든 숫자를 더하거나 뺀 후(sum이 최종적으로 계산된 후), sum이 target과 같은지 확인합니다.
    같다면 answer를 증가시킵니다.

이렇게 모든 숫자를 더하거나 빼는 모든 경우의 수를 탐색하여, 그중 합이 target과 같은 경우의 수를 찾습니다.

이 과정을 통해 [4, 1, 2, 1]에서
숫자들을 더하거나 빼서 4를 만드는 경우의 수는 2가지([4, -1, 1, 1]와 [-4, 1, 2, 1])임을 알 수 있습니다.

따라서, 최종적으로 answer는 2가 됩니다.

디테일한 계산 단계입니다.

1. dfs 함수를 처음 호출: dfs(0, 0)

2. index 0에서 숫자 4를 선택:
  - 더하는 경우: dfs(1, 4)
  - 빼는 경우: dfs(1, -4)

3. index 1에서 숫자 1을 선택:
  - dfs(1, 4)에서 더하고 빼는 경우 각각: dfs(2, 5), dfs(2, 3)
  - dfs(1, -4)에서 더하고 빼는 경우 각각: dfs(2, -3), dfs(2, -5)

4. index 2에서 숫자 2를 선택:
  - dfs(2, 5)에서 더하고 빼는 경우 각각: dfs(3, 7), dfs(3, 3)
  - dfs(2, 3)에서 더하고 빼는 경우 각각: dfs(3, 5), dfs(3, 1)
  - dfs(2, -3)에서 더하고 빼는 경우 각각: dfs(3, -1), dfs(3, -5)
  - dfs(2, -5)에서 더하고 빼는 경우 각각: dfs(3, -3), dfs(3, -7)

5. index 3에서 숫자 1을 선택:
  - dfs(3, 7)에서 더하고 빼는 경우 각각: dfs(4, 8), dfs(4, 6)
  - dfs(3, 3)에서 더하고 빼는 경우 각각: dfs(4, 4), dfs(4, 2) --> dfs(4, 4)는 target과 일치하므로 answer 증가
  - dfs(3, 1)에서 더하고 빼는 경우 각각: dfs(4, 2), dfs(4, 0)
  - dfs(3, -1)에서 더하고 빼는 경우 각각: dfs(4, 0), dfs(4, -2)
  - dfs(3, -3)에서 더하고 빼는 경우 각각: dfs(4, -2), dfs(4, -4)
  - dfs(3, -5)에서 더하고 빼는 경우 각각: dfs(4, -4), dfs(4, -6) --> dfs(4, -4)는 target과 일치하므로 answer 증가
  - dfs(3, -7)에서 더하고 빼는 경우 각각: dfs(4, -6), dfs(4, -8)

6. 모든 숫자를 더하거나 뺀 후(index가 numbers.length에 도달한 후), sum이 target과 같은지 확인합니다.
    같다면 answer를 증가시킵니다.

 

forEach는 배열을 순회하는 방법 중 하나입니다.

forEach()
map과 달리 return 값이 없다 는 특징을 가진다.

기본형
arr.forEach(function callback(curVal [, curIdx [, array]]) { }
→ callback : 배열의 각 요소에 실행할 함수
→ curVal : 처리할 현재 요소
→ index : 처리할 현재 요소의 인덱스
→ array : forEach가 호출된 배열

 

forEach 활용 (기본 편)

// 배열의 모든 요소 출력하기
const arr = [1, 2, 3, 4, 5];
arr.forEach(item => {
  console.log(item);
});

// 결과
// 1
// 2
// 3
// 4
// 5

// 배열의 모든 요소 2개로 만들기
const doubled = [];
arr.forEach(item => {
  doubled.push(item * 2);
});
console.log(doubled);

// 결과 : [2, 4, 6, 8, 10]

// 배열의 모든 요소와 그에 해당하는 인덱스 출력하기
const arr = ['apple', 'banana', 'cherry'];
arr.forEach((item, index) => {
  console.log(`인덱스 ${index}번 : ${item}`);
});

// 결과
// "인덱스 0번 : apple"
// "인덱스 1번 : banana"
// "인덱스 2번 : cherry"

// 배열의 모든 요소를 사용해 새 객체 생성하기
const arr = ['apple', 'banana', 'cherry'];
const obj = {};
arr.forEach((item, index) => {
  obj[index] = item;
});
console.log(obj);

// 결과
// {0: 'apple', 1: 'banana', 2: 'cherry'}

// 중첩된 배열을 사용 1
const arr = [[1, 2], [3, 4], [5, 6]];
arr.forEach(subArr => {
  subArr.forEach(item => {
    console.log(item);
  });
});

// 결과
// 1
// 2
// 3
// 4
// 5
// 6

// 중첩된 배열을 사용 2
const arr = [['apple', 'banana'], ['orange', 'lemon'], ['grape', 'kiwi']];
let newArr = [];
arr.forEach(subArr => {
  subArr.forEach(item => {
    newArr.push(item.toUpperCase());
  });
});
console.log(newArr);

// 결과
// ['APPLE', 'BANANA', 'ORANGE', 'LEMON', 'GRAPE', 'KIWI']

// 배열 요소를 조건에 따라 필터링한 경우
const arr = [1, 2, 3, 4, 5];
let evenNumbers = [];
arr.forEach(num => {
  if (num % 2 === 0) {
    evenNumbers.push(num);
  }
});
console.log(evenNumbers); 

// 결과
// [2, 4]

 

forEach 활용 (중급 편)

// forEach와 중첩 배열 : 중첩된 배열의 모든 요소에 1을 더하는 작업
const arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
arr.forEach(subArr => {
  subArr.forEach((item, index, array) => {
    array[index] = item + 1;
  });
});
console.log(arr);

// 결과
// [[2, 3, 4], [5, 6, 7], [8, 9, 10]]

// forEach와 reduce : 배열의 각 요소의 빈도수를 계산
const arr = ['apple', 'banana', 'apple', 'orange', 'banana', 'orange', 'apple'];
let count = {};
arr.forEach(item => {
  count[item] = (count[item] || 0) + 1;
});

console.log(count);

// 결과
// { apple: 3, banana: 2, orange: 2 }

// forEach와 splice : 배열의 짝수 요소를 삭제
const arr = [1, 2, 3, 4, 5];
arr.forEach((item, index, array) => {
  if (item % 2 === 0) {
    array.splice(index, 1);
  }
});
console.log(arr);

// 결과
// [1, 3, 5]