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

 

 

문제 파악

-주어진 배열을 끝까지 돌며 +,- 두 가지를 모두 구해 target값에 다다르는 경우의 수를 카운트

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

접근 방법

-완전 탐색이라서 dfs도 가능하지만, 큐가 조금 더 익숙해 큐로 풀이했다.

-기준 뽑아 연결 된 노드(경우의 수)를 모두 큐에 넣고 같은 조건에서 값을 누적해나갔을 때 결과값을 비교

-결과값이 맞기만 하면 카운트하면 되므로, 그냥 카운트한다.

코드 구현

import java.util.*;
class Solution {
    public int solution(int[] numbers, int target) {
        Queue<int[]> que=new ArrayDeque<>();
        int answer=0;
        //0 : 어디까지 순회했는지 체크할 인덱스 => 끝까지 다다랐을 때 값을 비교한다.
        //1 : sum값 누적
        que.add(new int[]{0,0});
        
        while(!que.isEmpty()){
            int[] node = que.poll();
            int idx = node[0];
            int sum = node[1];
            
            if(idx == numbers.length){
                if(sum==target){
                    answer++;
                }
            }else{
                que.add(new int[]{idx+1,sum+numbers[idx]});//for문없어도 인덱스를 바로 넣으면 됨,큐가 돌아가며 인덱스 역할한다.
                que.add(new int[]{idx+1,sum-numbers[idx]});
            }
        }
        return answer;
    }
}

(+ 추가)

 

dfs

-backtrack방식으로 한쪽으로 가다가, 다 돌았는데 타겟 아니면 리턴하기

import java.util.*;
class Solution {
    int cnt=0;
    public int solution(int[] numbers, int target) {
        backtrack(0,numbers,target,0); 
        return cnt;
    }
    public void backtrack(int idx,int[] numbers, int target,int sum){
        //base case
        if(idx>=numbers.length){
            if(sum==target){
                cnt++;
            }
            return;
        }
        //recursive call
        backtrack(idx+1,numbers,target,sum+numbers[idx]);
        backtrack(idx+1,numbers,target,sum-numbers[idx]);
        
    }
}

 

3트

import java.util.*;
class Solution {
int cnt=0;
public int solution(int[] numbers, int target) {
//backtrack방식으로 한쪽으로 가다가, 다 돌았는데 타겟 아니면 리턴하기
//다돌았는지 확인은 idx==numbers.length
//경우의 수 확인은 최종 누적이므로 멤버변수로 누적시키기
backtrack(0,0,numbers,target);
return cnt;
}
public void backtrack(int idx,int sum,int[] numbers, int target){
if(idx==numbers.length){
if(sum==target) cnt++;
return;
}
//경우의 수 2가지 -,+
backtrack(idx+1,sum+numbers[idx],numbers,target);
backtrack(idx+1,sum-numbers[idx],numbers,target);
}

}

배우게 된 점

-완전 탐색을 bfs로도 풀이가 가능하다는 점

-dfs 풀이는 나중에 천천히 해볼 예정이다. (⇒ 완료)

-인덱스 중요성!