프로그래머스: 타겟넘버

2020/06/15

문제

https://programmers.co.kr/learn/courses/30/lessons/43165

코드

public int solution(int[] numbers, int target) {
    int answer = dfs(numbers, target, 0, 0);
    return answer;
}

private int dfs(int[] numbers, int target, int depth, int sum) {
    if (depth == numbers.length) {
        return sum == target ? 1 : 0;
    }

    int left = dfs(numbers, target, depth + 1, sum + numbers[depth]);
    int right = dfs(numbers, target, depth + 1, sum - numbers[depth]);

    return left + right;
}

흐름

DFS 알고리즘 (재귀) 으로 해결
array index를 depth로 치고 모든 경우의 수를 탐색

0 번째 인덱스부터 시작
depth가 array length와 같으면 제일 깊은 곳 까지 모두 탐색한 것이므로
합이 target과 같은 지 판단해서 같으면 1, 다르면 0을 return
depth가 length와 다르면, 더 깊이 들어가야 하므로 dfs() 메서드를 depth + 1 하고 해당 깊이 까진 더 한 값을 파라미터로 넘김
2번부터 다시 반복
끝

마지막 return 부연 설명

1
2
3

if (depth == numbers.length) {
    return sum == target ? 1 : 0;
}

이미지 출처 https://lkhlkh23.tistory.com/74

맨 아래에서 맨 왼쪽 1+1+1+1+1은 3이 아니므로 0
그 옆 1+1+1+1-1은 3이므로 1 return
그럼 그 윗 노드인 1+1+1+1은 1
다음 탐색 순서인 1+1+1-1+1은 3이므로 1 return
1+1+1-1-1 = 1 이므로 0 return
이들의 부모 노드인 1+1+1-1은 1
그 위 부모 노드는 1 + 1 이므로 2가 됨
이런 식으로 마지막 까지 올라가면 결국 +1에선 4, -1 에선 1 되서 정답인 5를 return하게 되고
실제로 양수로 시작하는 부분에선 4개의 경우가 3이 return 되고, 음수로 시작하는 경우에는 1이 return 되므로 정답임을 알 수 있다.

결과

번호	속도
테스트 1	통과 (6.69ms, 54.4MB)
테스트 2	통과 (6.56ms, 52.9MB)
테스트 3	통과 (0.97ms, 52.8MB)
테스트 4	통과 (1.26ms, 50.9MB)
테스트 5	통과 (1.75ms, 50.1MB)
테스트 6	통과 (1.00ms, 52.3MB)
테스트 7	통과 (0.93ms, 52.5MB)
테스트 8	통과 (1.44ms, 52.6MB)

테스트 케이스

assertEquals(5, test.solution(new int[] {1,1,1,1,1}, 3));
assertEquals(3, test.solution(new int[] {2,3,5,7,9}, 2));
assertEquals(1, test.solution(new int[] {1}, 1));
assertEquals(5, test.solution(new int[] {6,2,3,6,7,1}, 7));

참고 사이트

댓글 공유

프로그래머스: 타겟넘버

문제

코드

흐름

마지막 return 부연 설명

결과

테스트 케이스

참고 사이트

Junggu Ji