[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
[4, 1, 2, 1]	4	2

 

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

---

문제 분석해보기

최근 문제 풀이에서는 문제 분석을 하고, 의사 코드를 작성해본 뒤에 문제를 풀어보고 있어서 그 내용을 공유해볼까 한다.

 

제약사항 및 핵심 키워드 파악하기

• 주어진 숫자를 순서대로 사용해야 한다.
• 더하거나 빼서 특정 target 값을 만든다.
• 가능한 모든 경우의 수를 탐색해야 한다.

요구사항과 제약사항을 읽고 가져와보았다. 이 중에서 '가능한 모든 경우의 수를 탐색해야 한다.' 라는 키워드를 보고 DFS 또는 BFS를 사용해서 문제를 풀면 되겠다고 생각했다.

 

그러면 이제 간단하게 코드 흐름을 작성해볼 수 있을 것 같다.

 

동작 단위로 쪼개기

• 숫자 하나씩 탐색하기
  • 현재 숫자를 더한다.
  • 현재 숫자를 뺀다.
• 모든 숫자를 처리했을 때 검사하기
  • 누적값이 target과 같은지 확인한다.
• 같을 경우 조합의 갯수를 더해서 누적하기

이렇게 작성해본 의사 코드에 맞게, 실제 DFS코드로 구현하면 아래와 같이 나온다.

 

나의 문제 풀이

function solution(numbers, target) {
    var answer = 0;
    
    dfs(0,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]);
        
    }
    
    return answer;
}

 

입력 예시인 [4, 1, 2, 1] 과 target 4를 가지고 동작을 설명해보도록 하겠다.

입력값 예시 [4, 1, 2, 1]과 target 4에 대한 트리

 

배열의 순서대로 위와 같은 트리가 구성되어 있고, 이를 깊이 우선 탐색으로 조합을 찾아나가는 거라고 생각하면 된다.

0은 sum의 초기값 0에 대한 시작이다.

 

트리를 아래와 같은 순서로 탐색한 후, 끝까지 탐색했을 때

즉, if(index === numbers.length) 일때의 sum의 값을 확인하는 것이다.

+4 +1 +2 +1 = 8
+4 +1 +2 -1 = 6 
+4 +1 -2 +1 = 4 // 달성
+4 +1 -2 -1 = 2
+4 -1 -2 +1 = 2
+4 -1 -2 -1 = 0
+4 -1 +2 +1 = 6
+4 -1 +2 -1 = 4 // 달성
-4 +1 +2 +1 = 0
-4 +1 +2 -1 = -2
-4 +1 -2 +1 = -4
-4 +1 -2 -1 = -6
-4 -1 -2 +1 = -6
-4 -1 -2 -1 = -8
-4 -1 +2 +1 = -2
-4 -1 +2 -1 = -4

 

문제풀이 소감

https://product.kyobobook.co.kr/detail/S000213641007

코딩 테스트 합격자 되기: 자바스크립트 편 | 이선협 - 교보문고

 

최근 이 책을 통해서 코딩 테스트를 공부하고 있다. 코딩 테스트의 코드를 작성하기 전에 문제 분석을 하고 어떤 알고리즘을 사용하는 것이 가장 효율적인 방법일지 파악하는 것이 중요하다고 이야기했다.

 

내가 이전까지 풀었던 문제들 중에서 비교적 어려운 문제였는데, 차근차근 쪼개서 분석하고 수도 코드를 작성한 뒤 실제 코드를 작성하니 그렇게 어렵게 느껴지지 않았던 것 같다.

 

사실 큐를 이용해서 BFS로 구현하는 것보다 재귀로 DFS 구현하는게 비교적 더 익숙해서 그렇게 바로 풀었는데, BFS로 풀면 시간 초과가 뜬다고 한다 하하 !

 

앞으로 코테 준비도 꾸준히 열심히 해서 기회가 왔을 때 잡을 수 있는 사람이 되고 싶다 ! 

 

그럼 오늘은 이만 ~!

안뇽 !