프로그래머스 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 이하인 자연수입니다.

 

 

입출력 예

---

[1, 1, 1, 1, 1] , 3 5
[4, 1, 2, 1] , 4 2

 

 

 

나의 생각

---

각 배열은 각각 다음 정수의 음의 값과 양의 값을 더해나가며 진행하므로, 각 노드 당 경우의 수는 2가지 이고, 이진 트리 구조가 완성됩니다. 

여기서 BFS를 떠올리게 되었고, 큐에 각각 더해진 값들을 이용하여 저장하고, 깊이가 1 증가할수록, 인덱스를 증가시키고, 다음 반복 때 큐의 크기만큼 순회하며, 인덱스가 배열의 크기와 같아질 때, 반복을 멈추고 map함수를 이용하여 타겟 넘버와 일치하는 수만큼 answer를 증가시켜 리턴해주었습니다.

 

 

코드

---

import java.util.*

class Solution {
    val queue: Queue<Int> = LinkedList() // 값을 저장할 큐 선언
    lateinit var nums: IntArray // 문제의 배열을 저장할 전역 배열
    
    fun bfs(start: Int, target: Int): Int {
        var answer = 0 // 후에 리턴해줄 정답 갯수
        var index = 0 // 깊이를 정해줄 값
        queue.add(start) // 시작 값을 큐에 넣어둠
        
        while (queue.isNotEmpty()) {
            if (index == nums.size) {
                break
            } // 인덱스(깊이)가 사이즈와 같으면 반복문 탈출
            val intCount = queue.size // 매 반복마다 큐의 크기만큼 돌 수 있도록 저장
            for (i in 0 until intCount) {
                val q = queue.poll() // 맨 앞의 값을 하나 제거하고 저장
                queue.add(q + nums[index]) // 더한 값을 다시 저장
                queue.add(q - nums[index]) // 뺀 값을 다시 저장
            }
            index += 1 // 깊이 1 증가
        }
        
        queue.map {
            if (it == target)
                answer++
        } // 남아있는 큐에서 타겟 넘버와 같은 값이 있을 경우, answer를 증가
        
        return answer
    }
    
    fun solution(numbers: IntArray, target: Int): Int {
        nums = numbers // 전역 변수에 저장
        return bfs(0, target) // 0 (트리의 루트 값)과, 타겟 넘버를 매개 변수 인자로 넘겨줌 
    }
}