프로그래머스 Lv2. 타겟 넘버

 

- 문제 설명
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 합니다.

 

- 풀이 과정

 

처음 이 문제를 봤을 때, 어떻게 풀어야 할지 감이 잡히지 않아서 검색해보았고 DFS와 BFS 알고리즘을 공부해야 함을 알게됐다. 두가지의 코드 방식과 함께 살펴보자.

 

1. BFS (너비 우선 탐색)

가까운 노드부터 점차적으로 탐색하는 방식이다.

최단 경로 찾기 문제에 유리하며 보통 Queue를 통해 만들어 진다.

1-1. int[]로 넣는 방법

numbers = [1,1] 

target = 2

 

• len = 0, sum = 0
  
  • sum + numbers[0] = 0 + 1 = 1을 큐에 넣음: [1, 1]
  • sum - numbers[0] = 0 - 1 = -1을 큐에 넣음: [1, -1]
  • 큐 상태: [(1, 1), (1, -1)]
• len = 1, sum = 1
  • sum + numbers[1] = 1 + 1 = 2을 큐에 넣음: [2, 2]
  • sum - numbers[1] = 1 - 1 = 0을 큐에 넣음: [2, 0]
  • 큐 상태: [(1, -1), (2, 2), (2, 0)]
• len = 1, sum = -1
  • sum + numbers[1] = -1 + 1 = 0을 큐에 넣음: [2, 0]
  • sum - numbers[1] = -1 - 1 = -2을 큐에 넣음: [2, -2]
  • 큐 상태: [(2, 2), (2, 0), (2, 0), (2, -2)]
• len = 2, sum = 2
  • answer ++; 

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        
        while (!q.isEmpty()) {
            int[] now = q.poll();
            int len = now[0]; 
            int sum = now[1];
            
            if (len == numbers.length) {
                if (sum == target) answer++;
            } else {
                q.offer(new int[]{len + 1, sum + numbers[len]});
                q.offer(new int[]{len + 1, sum - numbers[len]});
            }
        }
        return answer;
    }
}

 

1-2. Integer로 넣는 방법

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(0);
        q.offer(0);
        
        while (q.peek() != null){
            int len = q.poll();
            int sum = q.poll();
            
            if (len == numbers.length){
                if(sum == target) answer++;
            } else {
                q.offer(len + 1);
                q.offer(sum + numbers[len]);
                q.offer(len + 1);
                q.offer(sum - numbers[len]);
            }
        }
        return answer;
    }   
}

 

 

2. DFS (깊이 우선 탐색)

한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 단계로 되돌아가 다른 경로를 탐색하는 방식이다.

미로 찾기 문제에 유리하며 보통 재귀함수를 통해 만들어 진다.

 

numbers = [1,1] 

target = 2

 

• len = 0, sum = 0 :
  • sum = 0 + 1 = 1 , sum = 0 - 1 = -1 (첫 번째 1을 더하고 뺌)
• 첫 번째 호출: len = 1
  
  • sum = 1 + 1 = 2, sum = 1 - 1 = 0 (첫 번째 호출 1에 더하고 뺌) > 두번째 호출에서 1반환 , 0반환
  • sum = -1 + 1 = 0, sum = -1 - 1 = -2 (첫 번째 호출 -1에 더하고 뺌) > 두번째 호출에서 0반환, 0반환
• 세 번째 호출: len = 2
  
  • sum = 2 + 1 = 3, sum = 2 - 1 = 1 (첫 번째에 첫번째 호출 2에서 더하고 뺌)
  • sum = 0 + 1 = 1, sum = 0 - 1 = -1 (첫 번째에 첫번째 호출 0에서 더하고 뺌)
  • sum = 0 + 1 = 1, sum = 0 - 1 = -1 (첫 번째에 두번째 호출 0에서 더하고 뺌)
  • sum = -2 + 1 = -1, sum = -2 - 1 = -3 (첫 번째에 두번째 호출 -2에서 더하고 뺌)

 

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private int dfs(int[] numbers, int target, int len, int sum) {
        if (len == numbers.length) {
            return sum == target ? 1 : 0;
        }
        return dfs(numbers, target, len + 1, sum + numbers[len])
             + dfs(numbers, target, len + 1, sum - numbers[len]);
    }
}