문제 ]
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 이하인 자연수입니다.
DFS와 BFS ]
[ DFS ]
깊이 우선 탐색(depth-first search)은 맹목적 탐색방법의 하나로, 노드가 트리일시 좌측노드를 기점으로 깊이 제한에 도달할 때 까지 목표노드를 찾는다. 제한 깊이까지 목표노드가 발견되지 않으면 최근노드의 부모노드로 되돌아가서 거치지 않은 다른 자식노드로 탐색을 시작한다. 여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라고 한다.
- 장점
- 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
- 단점
- 얻어진 해가 최단 경로가 아닌 노드 전체를 탐색해야하는 경우가 있을 수 있다. 즉 최적의 방법으로 구한 해는 아닐 수 있다.
[ BFS ]
너비 우선 탐색(Breadth-first search)은 맹목적 탐색방법의 하나로, 루트 노드를 방문한 후 인접한 모든 노드들을 우선적으로 검색하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때 까지 검색을 하는데 트리의 너비를 기준으로 검색한다.
- 장점
- 출발 노드에서 목표노드까지의 최단 길이 경로를 보장한다.
- 단점
- 너비경로가 길 경우 탐색가지가 증가함에 따라 보다 많은 기억 공간이 필요하다.
제출 DFS ]
class Solution {
public int solution(int[] numbers, int target) {
int current = numbers[0];
int answer = 0;
answer += dfs(current, 1, numbers, target);
answer += dfs(-current, 1, numbers, target);
return answer;
}
public int dfs(int prev, int index, int[] numbers, int target){
if(index >= numbers.length){
if(target==prev) return 1;
return 0;
}
int cur1 = prev + numbers[index];
int cur2 = prev - numbers[index];
int ans = 0;
ans += dfs(cur1, index+1, numbers, target);
ans += dfs(cur2, index+1, numbers, target);
return ans;
}
}
풀이 DFS ]
재귀를 이용하여 DFS를 활용한다.
제출 BFS ]
import java.util.Queue;
import java.util.LinkedList;
class Solution {
class Pair{
int cur;
int index;
Pair(int cur, int index){
this.cur = cur;
this.index = index;
}
}
public int solution(int[] numbers, int target) {
int answer = 0;
Queue<Pair> queue = new LinkedList<Pair>();
queue.offer(new Pair(numbers[0],0));
queue.offer(new Pair(-numbers[0],0));
while(!queue.isEmpty()){
Pair p = queue.poll();
if(p.index == numbers.length-1){
if(p.cur == target){
answer += 1;
}
continue;
}
int c1 = p.cur + numbers[p.index+1];
int c2 = p.cur - numbers[p.index+1];
queue.add(new Pair(c1, p.index+1));
queue.add(new Pair(c2, p.index+1));
}
return answer;
}
}
Queue는 인터페이스 형태로 LinkedList를 통해 생성한다. FIFO(Firtst in first out)이 큰 특징이다.
Class Pair를 원소로 하는 Queue를 이용하여 너비우선탐색을 실행한다. Pair클래스는 깊이를 나타내는 index와 해당 값 (1 +1 +1 -1 ...)을 나타내는 cur를 변수로 가진다.
Index가 numbers길이와 같다면 cur를 target값과 비교해 일치하는지 확인하여 answer에 값을 +할지 안할지 결정한다.
댓글 없음:
댓글 쓰기