[프로그래머스] 타겟 넘버 - Java

• 타겟 넘버

풀이과정

• 문제에 주어진 예제 2번을 살펴보면 다음과 같은 그림을 그릴 수 있다. (주어진 조건 : numbers = {4, 1, 2, 1}, target 4)
  

  

• 0에서부터 주어진 숫자들을 +, - 해 나가는 Tree를 만든 후(BFS) 최종 결과값을 확인하며 target과 일치하는 것의 갯수를 세면 정답을 찾을 수 있다.

Code

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int solution(int[] numbers, int target) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);

        for (int number : numbers) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int currentValue = queue.poll();
                queue.offer(currentValue + number);
                queue.offer(currentValue - number);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            if (queue.poll() == target) {
                count++;
            }
        }

        return count;
    }
}

결과