반응형
문제
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 (트리의 루트 값)과, 타겟 넘버를 매개 변수 인자로 넘겨줌
}
}
728x90
반응형
'CodingTest' 카테고리의 다른 글
LIS (최장 증가 부분 수열) (1) | 2025.01.27 |
---|---|
프로그래머스 2레벨 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 (0) | 2024.09.09 |
Binary Search (이진 탐색) (2) | 2024.09.09 |
프로그래머스 3레벨 - 네트워크 (1) | 2024.09.08 |
BFS, DFS (깊이 우선 탐색, 너비 우선 탐색) (3) | 2024.09.07 |