문제 링크

문제 간단 해석

DFS / BFS 문제.

Java

stack을 활용한 DFS.

풀이 코드

import java.util.Stack;

class Solution {
    class Pair {
        private int now = 0;
        private int idx = 0;

        public Pair(int now, int idx) {
            this.now = now;
            this.idx = idx;
        }

        public int getNow() {
            return now;
        }

        public int getIdx() {
            return idx;
        }

    }
    public int solution(int[] numbers, int target) {

        Stack<Pair> stack = new Stack<>();
        stack.add(new Pair(0, 0));
        Pair pair;
        int idx, now, answer = 0;

        while (stack.size() != 0) {
            pair = stack.pop();
            now = pair.getNow();
            idx = pair.getIdx();

            if (idx == numbers.length) {
                if (now == target)
                    answer++;
            } else {
                stack.add(new Pair(now + numbers[idx], idx + 1));
                stack.add(new Pair(now - numbers[idx], idx + 1));
            }

        }

        return answer;
    }
}

해석

class Pair {
    private int now = 0;
    private int idx = 0;

    public Pair(int now, int idx) {
        this.now = now;
        this.idx = idx;
    }

    public int getNow() {
        return now;
    }

    public int getIdx() {
        return idx;
    }

}

현재값과 idx를 담을 Pair 선언.
idx는 numbers의 index를 나타내며, 이번 연산에서 처리할 숫자를 지정한다.

Stack<Pair> stack = new Stack<>();
stack.add(new Pair(0, 0));
Pair pair;
int idx, now, answer = 0;

스택에 현재값과 idx가 0인 Pair를 넣어놓고, 값을 받을 객체들을 선언했다.

while (stack.size() != 0) {
    pair = stack.pop();
    now = pair.getNow();
    idx = pair.getIdx();

    if (idx == numbers.length) {
        if (now == target)
            answer++;
    } else {
        stack.add(new Pair(now + numbers[idx], idx + 1));
        stack.add(new Pair(now - numbers[idx], idx + 1));
    }

}

return answer;

모든 값들이 다 처리되어 stack이 빌 때까지 돌린다.
stack의 마지막값을 받아와 now, idx를 얻는다.
만약 idx가 numbers의 길이와 같다면(모든 numbers 값을 연산했다면) 더 이상 연산해 줄 값이 없으니 결과를 확인한다.
만약 최종값이 target과 같다면, answer를 1 늘려준다.

아직 처리해야할 값이 있다면 해당 값에 대해 +, - 연산을 수행, stack에 넣는다.

stack이 텅 비었다면 target과 같은 값을 가졌던 횟수를 반환.

Python

재귀를 활용한 DFS.

풀이 코드

def solution(numbers, target):
    N = len(numbers)
    ans = 0

    def makeTargetNumber(i=0, total=0):
        if i == N:
            if total == target:
                nonlocal ans
                ans += 1
            return
        makeTargetNumber(i + 1, total + numbers[i])
        makeTargetNumber(i + 1, total - numbers[i])

    makeTargetNumber()
    return ans

해석

N = len(numbers)
ans = 0

배열의 길이 N과 return값을 결정할 ans 선언.

def makeTargetNumber(i=0, total=0):
    if i == N:
        if total == target:
            nonlocal ans
            ans += 1
        return
    makeTargetNumber(i + 1, total + numbers[i])
    makeTargetNumber(i + 1, total - numbers[i])

재귀함수 선언.
만약 재귀횟수가 N과 같아 더 이상 처리할 값이 없다면 최종값을 확인한다.
최종값이 target과 같다면 ans에 1을 더해준다.
nonlocal은 해당 범위(재귀함수)내에 일치하는 변수가 없다는 것을 알려준다.
따라서 solution 내에서 선언한 ans를 가리킨다.

아직 처리할 값이 남아있다면 +, - 연산하여 다시 재귀를 호출한다.

makeTargetNumber()
return ans

재귀함수 시작, ans 반환.

여담

Python을 하며 재귀를 싫어하게 되었는데(stack에 비해 이점이 없다고 생각했음), Java를 보니 재귀가 나쁘지만은 않은 것 같다. 코드 구성이 압도적으로 짧아지는 이점이 있더라.. 다음부터는 재귀를 적극 활용해봐야겠다.