[코딩테스트 일지 - 99클럽] 5일차 - 타겟 넘버

코딩 테스트 준비 일지 5 일차

• 응시 사이트 : 프로그래머스

• 문제 : 타겟 넘버

• 난이도 : 중

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

[4, 1, 2, 1] 4 2

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

문제 풀이 접근

결과적으로 오늘 혼자 풀었느냐 하면 아니다.

문제를 보자마자, 핵심 키워드를 확인을 해보니 DFS/BFS 였다.
문제에서 나타난 핵심은
1. 순서는 그대로다.
2. 타겟 넘버에 맞다면, 여기서 카운트 하나 올리고, 총 카운트를 리턴한다.

이 문제를 풀면서 어느정도 트리를 생각하여 계속 트리를 그리고 왜 스왑이 없지? 경로들은 어떻게 담지?
하면서 문제에서도 요구하지 않은 사양에 빠져있었다.

그리하여 문제 푸는시간이 약 1시간 40분 정도 걸렸고, 같은 반에 있으신 분께 도움을 받았다.
도움 받고 다시 문제 푸는 방식을 정립하고 아래와 같이 나왔다.

1. 경로를 담을 필요는 없다.

2. 스왑도 생각하지마라. 왜 생각하는겨

3. + - 경우를 더하면서 재귀돌리면 된다.

정답 작성 코드 ( C# )

using System;
using System.Collections.Generic;
public class Solution
{
public int solution(int[] numbers, int target)
{
int answer = 0;
calc(numbers, 0, 0, target, ref answer);
return answer;
}
public static void calc(int[] arr, int sum, int depth, int target, ref int answer)
{
if((arr.Length == depth) && (sum == target))
{
++answer;
return;
} // 뎁스가 마지막에 도달했으며, 여기서 타겟넘버와 값이 같을때, ++ 한다    if (arr.Length <= depth)
        return; // 뎁스가 길이를 넘어갔을때, 종료한다.

    calc(arr, sum + arr[depth], depth + 1, target, ref answer); 
    // + 의 경우
    calc(arr, sum + (arr[depth] * -1), depth + 1, target, ref answer);
}}

코드 결과