프로그래머스 문제:타켓 넘버

 

 

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

프로그래머스

 

function solution(numbers, target) {
  // 최종 결과를 저장할 변수, 초기값 0으로 설정
  let answer = 0;

  // 깊이 우선 탐색(DFS) 재귀 함수 정의
  const dfs = (index, sum) => {
    // 배열의 모든 원소를 탐색했을 때 
    if (index === numbers.length) {
      // 현재 합계가 target과 정확히 일치하면
      if (sum === target) answer++;
      // 더 이상 탐색할 원소 없으므로 종료
      return;
    }

    // 첫 번째 재귀 호출: 현재 숫자를 더하는 경우
    // 인덱스 1 증가, 현재 숫자를 sum에 더함
    dfs(index + 1, sum + numbers[index]);

    // 두 번째 재귀 호출: 현재 숫자를 빼는 경우
    // 인덱스 1 증가, 현재 숫자를 sum에서 뺌
    dfs(index + 1, sum - numbers[index]);
  };

  // 초기 인덱스 0, 초기 합계 0으로 DFS 시작
  dfs(0, 0);

  // 타겟 합을 만들 수 있는 총 경우의 수 반환
  return answer;
}

 

카테고리를 보니까 깊이/너비 우선탐색 알고리즘이길래 그걸 써야하는가보다 하고 써봤다.

 

배열의 첫번째 숫자부터 -/+인 경우의수 2개로 시작해서 첫번째가 -일때 두번째가 -/+인 경우의수, 첫번째가 +일때 두번째가 -/+인 경우의수 그러니까 O(2^n)의 시간복잡도를 갖는다.

 

예시:[1,1,1,1,1]일때

 

첫번째 숫자까지

+1

-1

 

두번째 숫자까지

+1-1

+1+1

 

-1+1

-1-1

 

....

이런식으로 합을 찾고 그 합이 타겟넘버라면 answer을 1 증가시킨다.