코딩 테스트 준비 일지 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분 정도 걸렸고, 같은 반에 있으신 분께 도움을 받았다.
도움 받고 다시 문제 푸는 방식을 정립하고 아래와 같이 나왔다.
경로를 담을 필요는 없다.
스왑도 생각하지마라. 왜 생각하는겨
+ - 경우를 더하면서 재귀돌리면 된다.
정답 작성 코드 ( 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);
}}코드 결과
