[PG] 타겟 넘버 JAVA

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

코딩테스트 연습 - 타겟 넘버

사용할 수 있는 숫자들의 배열 int[] numbers, int target 가 주어진다.

numbers 의 원소들을 사용해 덧셈, 뺄셈 연산을 적절히 수행했을 때 target을 만들어낼 수 있는 모든 경우의 수의 개수를 반환해야한다.

numbers의 원소는 모두 음이 아닌 정수이다.

 

 

 

풀이 1. (틀린 코드)

class Solution {
    // numbers의 원소들의 순서를 유지하지 않는 경우(모든 순열 구하는 방식)
    // 이 문제에선 틀린 코드임 (시간초과)
    
    int answer = 0;
    boolean[] check = null;
    
    public void DFS(int dept, int[] numbers, int target, int calc) {
        if(dept == numbers.length) {
            if(calc == target) {
                answer++;
            }
            return;
        }
        
        // 모든 순열을 구하기 위해 백트래킹 사용
        for(int i = 0; i < numbers.length; i++) {
            if(check[i] == false) {
                check[i] = true;
                DFS(dept + 1, numbers, target, calc + numbers[i]);
                DFS(dept + 1, numbers, target, calc - numbers[i]);
                check[i] = false;
            }
        }
    }
    
    public int solution(int[] numbers, int target) {
        check = new boolean[numbers.length];
        DFS(0, numbers, target, 0);
        return answer;
    }
}

 

문제의 조건이 제대로 명시되지 않아 틀린 코드를 작성했다.

 

numbers의 원소들이 사용되는 순서에 대한 아무런 언급이 없었기에 당연하게 원소들의 순서가 유지되지 않는, 즉, 모든 순열을 고려하는 방식으로 코드를 작성했다. 

 

그리고 시간초과를 맞이했다. numbers의 최대 길이는 20이다. + 연산만 하는 경우라고 해도 최대 20! 개의 식을 구하게 된다. 당연히 시간초과...

(물론 + 연산만 하면 모든 식의 결과가 같을 테니 무의미하긴 하지만 식의 개수에 대해 얘기하는 것이니..)

 

처음부터 이 계산을 해보고 뭔가 이상하단 걸 눈치 챘어야 했는데 무식하게 그냥 무작정 코딩했다. 

 

 

 

풀이 2. (정답 코드)

class Solution {
    int answer = 0;

    public void dfs(int dept, int calc, int[] numbers, int target) {
        if (dept == numbers.length) {  // 모든 원소를 반드시 전부 사용해야한다
            if (calc == target) {
                this.answer++;
            }
            return;
        }

        // 배열 내의 순서를 그대로 유지하며 +, - 연산을 이어나간다
        dfs(dept + 1, calc + numbers[dept], numbers, target);
        dfs(dept + 1, calc - numbers[dept], numbers, target);
    }

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

정답 코드이다.

 

아마 덧셈, 뺄셈은 항의 순서가 식의 결과에 영향을 미치지 않기 때문에 굳이 모든 순열을 구하지 않아도 되는 식으로 문제를 만든 것 같은데.. 그에 대한 설명이 너무 부실했다.

 

또, 배열의 모든 원소들을 반드시 다 사용하여야 한다는 규칙도 명시되지 않았다.

(이건 테스트 케이스에 간접적으로 드러나긴 했지만 그래도 따로 명시했어야 한다고 생각)

 

 

프로그래머스 문제는 이런 경우가 빈번히 발생하는 듯하다.