프로그래머스 43165 타겟 넘버 자바 풀이

난이도 : Lv. 2

풀이일 : 2411111

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

프로그래머스

---

문제

---

아이디어

• 모든 숫자에 대해 각 숫자를 빼거나 더한 값을 담아 다음 숫자에 넘겨준다.
• 다음 숫자에서는 넘겨받은 계산 값에 본인을 뺀 값, 더한 값 각각 다음 숫자한테 넘겨준다.
• 마지막 자리의 숫자를 더하거나 뺄 때는 해당 계산이 끝난 후, now가 target과 일치하는지 확인하여 answer 를 더한다.

---

풀이 코드

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

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int idx, now;
        
        // 이전까지 인덱스, 총합 저장할 큐 및 초기세팅
        Queue<Integer> queue = new LinkedList<>();
        queue.add(-1);
        queue.add(0);
        
        // 큐가 있는 동안 idx, now 추출
        while (!queue.isEmpty()) {
            idx = queue.poll();
            now = queue.poll();
            
            // 현재 idx가 마지막을 가리키면 continue
            if (idx == numbers.length - 1) {
            	// 현재 총합이 타겟과 같으면 answer++
                if (now == target) {
                    answer++;
                }
                continue;
            }
            // 다음 인덱스, 총계 - 현재값, 총계 + 현재값 큐 추가
            queue.add(idx + 1);
            queue.add(now - numbers[idx + 1]);
            queue.add(idx + 1);
            queue.add(now + numbers[idx + 1]);
        }
        return answer;
    }
}

• queue에 idx, 현재까지의 총계 넣어 다음 숫자에 전달
• 현재 idx가 마지막을 가리키면 continue하는데, 이때, now가 target과 같으면 answer를 하나 더해준다.
• 현재 idx가 마지막을 가리키지 않는다면, 다음 인덱스, 총계 - 현재값 쌍과 다음 인덱스, 총계 + 현재값 쌍을 큐에 추가한다.
• 큐에 있는 모든 요소를 검사하고 나면 answer를 출력한다.