깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

아래 문제는 프로그래머스에서 제공하는 코딩테스트 > 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버 (고득점 Kit)의 문제입니다🧑🏻‍💻

 

문제 제시

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

입출력 예

[1, 1, 1, 1, 1]

3

5

 

문제 해결

import Foundation

var number: [Int] = []
var targets: Int = 0
var count: Int = 0

func solution(_ numbers:[Int], _ target:Int) -> Int {
    number = numbers
    targets = target
    
    calculrate(index: 0, sum: 0)

    return count
}

func calculrate(index: Int, sum: Int) {
    if index == number.count {
        if sum == targets {
            count += 1
        }
        return
    }
    calculrate(index: index + 1, sum: sum + number[index])
    calculrate(index: index + 1, sum: sum - number[index])
}

사용된 개념

 - DFS

 - 조건문

 - 재귀함수

 

문제 뒷담화

이번 문제는 전체를 파악하는 트리같은 구조로 깊이탐색을 하는 문제였다.

즉 재귀함수 방법을 사용해야했다.

우선 재귀를 돌려줄 함수를 하나 더 정의하였다. 인덱스 값과 총합을 파라미터로 받는다.

만약 함수가 끝까지 돌아 인덱스가 배열의 수와 같아진다면 조건을 판별한다.

합이 주어진 타겟 정수와 같으면 카운트를 1 증가시키고 리턴하여 함수를 종료한다.

그렇게 정의해주고 해당 함수를 내부에서 재귀적으로 호출한다.

호출 시 +, - 를 해줘야함으로 두개의 함수 호출로 만든다. 그렇게 되면 가지처럼 알아서 재귀를 돈다.

그리고 메인 함수에서 해당 함수를 호출하는데 초기값으로 0을 인자로 전달해준다.

마지막으로 총 카운트를 반환하여 답을 도출해낼 수 있다.

재귀함수에 대해 자세히 몰랐던 부분을 반성하며 문제 파악의도를 먼저 생각해보았다.

어쨋든 전체 경우의 수를 계속 돌아야하는데 효율적으로 돌 방법을 생각해보다 재귀함수를 찾게되었다.

좀 더 알고리즘적으로 사고해보자!

 

 

[참고자료]

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