Today's Algorithm(2018-11-17)

programmers 타겟 넘버

뭔가 어려울줄 알았는데 막상 풀어보니 단순한 문제였네요. 결국은 모두 탐색해봐야하는 문제인데요. 이 경우 고려해볼 수 있는 것은 DFS를 고려해볼 수 있습니다. DFS를 구현하기 위해 재귀를 썼습니다. 하지만 구현을 하는데 있어 전역변수를 최대한 써보지 않는 방향으로 노력해봤는데 생각보다 잘 안되더라구요. 그래서 다 풀고나서 다른 사람들의 풀이를 참고하여 전역변수없이 구현하는 부분까지 해봤습니다.

 

class Solution {
    int answer, target;

    public int solution(int[] numbers, int target) {
        answer = 0;
        this.target = target;
        int[] sign = {-1, 1};

        visit(numbers, sign, numbers.length - 1, 0);
        return answer;
    }

    public void visit(int[] numbers, int[] sign, int index, int sum) {
        if(index < 0) {
            if(sum == target) answer++;
            return;
        }
        for (int i = 0; i < sign.length; i++) {
            visit(numbers, sign, index - 1, sum + (numbers[index] * sign[i]));
        }
    }
}

answer, target 이 두 개의 변수를 전역변수가 있었습니다. 이런 전역변수를 없애기 위해 visit() 함수의 return 값을 int 로 하고 모든 반환값들을 받아서 비교하려고 했는데 이게 재귀로 여러가지 경우를 제 각기 반환할 때 제일 마지막 값만 반환하더라구요. 그렇다보니 결국은 포기하고 전역변수로 제출을 했습니다.

 

public class Solution2 {

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

    int dfs(int[] numbers, int target, int sum, int index) {
        if (index < 0) {
            if (sum == target) return 1;
            else return 0;
        }

        return dfs(numbers, target, sum + numbers[index], index - 1) +
                dfs(numbers, target, sum - numbers[index], index - 1);
    }
}

결국 전역변수를 없애고 답을 내기 위해선 이 재귀 구조를 잘 설계해야 했습니다. 반환값을 제 각기 반환하는 것이 아니라 하나로 뭉쳐서(그 안에 재귀, 또 재귀 안에 재귀 이런 식으로) 반환해야 하는 것이었습니다. 위 코드에서 14, 15줄 부분이 그런 식으로 구현되어 있고 10줄, 11줄에서는 우리가 구하려는 값일 경우 1로 반환하고 아니면 0으로 반환해 종료 조건이 명시되어 있습니다. 피보나치 구조랑 유사하다는 생각이 듭니다. 그리고 위에서는 sign[] 배열이 존재했는데 Solution2와 같이 구현하면 그것도 필요없죠. 다음에 또 이런 문제를 풀게되면 제 힘으로 이렇게 세련되게 코드를 짤 수 있기를..