프로그래머스 타겟 넘버

코딩 테스트 준비를 안한지 너무 오래되서 슬슬 1일 1문제를 풀면서 감을 다시 찾아보려고 한다!

그리고 좀 체계적으로 준비하기 위해서 한 문제를 풀고 그 문제를 풀고 얻은 점을 블로그에 정리해보기 시작하려고 한다🔥🔥🔥

타겟 넘버

문제 설명

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 이하인 자연수입니다.

입출력 예

numbers target return
[1, 1, 1, 1, 1] 3 5
입출력 예 설명
문제에 나온 예와 같습니다.

numbers를 입력받는데 numbers는 + 혹은 -할 수 있다.
+, -를 선택할 수 있고 그 상태에서 또 +, -를 선택할 수 있다?
이 그림처럼 가지치기를 할 수 있는 형태라면 bfs를 떠올리자!

물론 dp로도 풀 수 있겠지만 나는 dfs가 더 편하고 익숙하기에,,,ㅎ dfs로 풀이해본다!

import java.util.*;		// Queue 사용을 위해서

// 현재 값과 인덱스를 저장할 수 있는 클래스를 선언한다.
class Pair
{	
    int cur;
    int ind;
    Pair(int cur, int ind)
    {
    	this.cur = cur;
        this.ind = ind;
    }
}

public int Solution(int numbers[], int target)
{
	int answers = 0;
    
    // Pair로 이루어진 queue 선언
    Queue<Pair> q = new LinkedList<Pair>();
    // 초기값 queue에 넣어주기
    q.offer(new Pair(numbers[0], 0));
    q.offer(new Pair(-1 * numbers[0], 0));
    
    // queue가 빌 때까지 반복
    while(!q.isEmpty())
    {
    	// queue 값 차례대로 꺼내기
    	Pair curP = q.poll();
        
        // pair의 인덱스가 마지막 인덱스일 때
        if (curP.ind == numbers.length - 1)
        {
        	// 타겟값과 일치하면 방법 하나 추가
        	if (curP.cur == target)
            	answer++;
                
              	// 아니면 지나가기
            	continue;
        }
        
        // 다음 numbers의 요소를 더했을 때와 뺐을 때의 값
        int next1 = curP.cur + numbers[curP.ind+1];
        int next2 = curP.cur - numbers[curP.ind+1];
        
        // queue에 더했을 때와 뺐을 때 추가
        q.offer(new Pair(next1, curP.ind+1));
        q.offer(new Pair(next2, curP.ind+2));
    }
}

한 줄 요약

가지치기 = BFS