[프로그래머스] 타겟 넘버(level 2, BFS)

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [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 합니다.

 

BFS

import java.util.*;  
  
class Solution {  
  
    public int solution(int[] numbers, int target) {  
        int answer = 0;  
        Queue<Integer> queue = new LinkedList<>();  
        queue.add(0);  
        for (int i = 0; i < numbers.length; i++) {  
            int size = queue.size();  
            for (int j = 0; j < size; j++) {  
                int sum = queue.poll();  
                queue.add(sum + numbers[i]);  
                queue.add(sum - numbers[i]);  
            }  
        }  
        while (!queue.isEmpty()) {  
            if (queue.poll() == target) {  
                answer++;  
            }  
        }  
        return answer;  
    }  
}

 

queue는 BFS 방식으로 탐지 중 각 단계에서의 합을 저장하는 큐다. 처음엔 0을 넣고 시작한다.

그리고 numbers 배열을 순회하면서 각 숫자에 대해 더하거나 빼는 연산을 진행한다.

 

 

 

각 단계마다 numbers[i]를 더하거나 빼는 두 가지 경우를 새로 큐에 추가한다.

 

 

• int sum = queue.poll(): 큐에서 현재 합을 꺼낸다.
• queue.add(sum + numbers[i]): 현재 합에서 numbers[i]를 더한 값을 큐에 추가한다.
• queue.add(sum - numbers[i]): 현재 합에서 numbers[i]를 뺀 값을 큐에 추가한다.

 

numbers 배열의 모든 숫자에 대해 BFS 탐색을 완료한 후에는

큐에 마지막까지 계산된 모든 가능한 합이 들어 있게 된다.

 

큐에 남은 값들을 하나씩 꺼내서 target 값과 일치하는지 확인하고

꺼낸 값이 target과 같으면 경우의 수를 증가시킨다.

 

 

참고

https://velog.io/@doxxx93/practice-kit-dfs-bfs-1

[프로그래머스] 타겟 넘버 - JAVA [자바]