타-겟 넘버

타-겟 넘버

 

프로그래머스 코딩 테스트 문제

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

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

 

 

1. 문제

문제 설명

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

 

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

 

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4

• 총 2가지 방법이 있으므로, 2를 return 합니다.

 

 

 

2. 풀이

DFS를 사용하여 +와 -를 분기점으로 간선을 이동하며 주어진 숫자 배열(numbers)의 순서대로 값들을 더하거나 뺀다.

경로의 끝에서 최종적으로 계산된 값과 target값을 비교하여 count를 늘린다.

 

위 방식으로 문제를 풀 때, 각 노드(+ 또는 -)가 가지고 있어야 할 정보는 계산될 숫자, 계산된 결과, 깊이(depth)라고 판단했다.

깊이는 현재 노드가 경로의 끝인지와 계산될 숫자를 주어진 숫자의 배열(numbers)에서 찾기 위함이다.

 

각 노드가 가지고 있어야할 정보를 Info라는 클래스로 만들었다.

 

[Info 클래스]

private class Info {
    int number;
    int result;
    int depth;

    public Info(int number, int result, int depth) {
        this.number = number;
        this.result = result;
        this.depth = depth;
    }

    private void cal() {
        result += number;
    }

    private void next(int[] numbers) {
        depth += 1;
        number = numbers[depth];
    }

    private boolean check(int target, int size) {
        if (result == target && depth == size - 1) {
            count++;
            return true;
        }
        if (depth == size - 1) {
            return true;
        }
        return false;
    }
}

Info 클래스는 필드로 number(현재 노드의 계산될 숫자), result(계산된 값), depth(깊이)를 갖고 있다.

 

● cal() : 현재 노드에서 계산될 숫자(number)를 현재 노드까지 계산된 값(result)에 더해 현재 노드에서 계산된 값으로 만든다.

● next(int[] numbers) : 다음 노드로 가기 위한 메서드. depth를 1 늘리고 number를 다음 노드의 숫자로 변경한다.

● check(int target, int size)

◎ 숫자 배열(numbers)과 현재 depth를 비교해서 마지막 노드인지를 확인한다.

◎ 동시에 현재 노드에서 계산된 값이 target과 일치하는지도 확인한다.

◎ 계산된 값이 target과 일치하면 전역 변수인 count를 1 증가시킨다.

◎ 계산된 값이 target과 일치하지 않아도 마지막 노드라면 탐색을 끝내기 위해 true를 반환한다.

 

 

[dfs]

private void dfs(Info info, int[] numbers, int target) {
    info.cal();
    if (info.check(target, numbers.length)) {
        return;
    }

    info.next(numbers);

    Info plus_temp = new Info(info.number, info.result, info.depth);
    Info minus_temp = new Info(-info.number, info.result, info.depth);


    dfs(plus_temp, numbers, target);
    dfs(minus_temp, numbers, target);
    return;
}

● 각 노드를 DFS로 탐색하는 메서드. 

● 해당 메서드에 들어온 것은 + 또는 - 노드에 방문했다는 것을 의미한다.

● 메서드에 info가 들어오면 cal()을 이용해 바로 해당 노드에서 계산되야될 값을 계산하고 info.result의 값을 경신한다.

● 이후 check() 메서드로 현재 노드가 마지막인지, target과 info.result가 일치하는 지를 확인하고 반환 값이 true라면 탐색을 멈춘다.

● 마지막 노드 가아니라면 next()를 이용해 info의 정보를 다음 노드에 넘길 number와 depth로 갱신한다.

● 기존의 DFS와 달리 노드를 방문만 하는 것이 아니라 number의 합을 계산하고 각 노드에서 그 값을 유지해야 하기 때문에 new Info()를 사용해서 다음 노드를 방문할 때 넘겨야 하는 info의 인스턴스를 생성하였다.

※ 만약 현재 노드(dfs메서드)에서 인스턴스를 생성하지 않고 info.number에 +,-만 붙여 다음 노드(dfs메서드)로 넘기면 계속 객체가 공유되어 변하기 때문에 각 노드의 Info 객체도 변하게 된다.

● 모든 계산과 처리가 끝나면 dfs()를 사용해 다음 +와 -노드로 이동한다.

 

 

[solution]

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

    Info plus_info = new Info(numbers[0], 0, 0);
    Info minus_info = new Info(-numbers[0], 0, 0);
    dfs(plus_info, numbers, target);
    dfs(minus_info, numbers, target);

    return count;
}

초기에 시작할 +, -값을 생성하고 dfs()에 넣어 count를 계산하고 반환한다.

 

 

[전체 코드]

public class Solution {

    static int count = 0;

    private class Info {
        int number;
        int result;
        int depth;

        public Info(int number, int result, int depth) {
            this.number = number;
            this.result = result;
            this.depth = depth;
        }

        private void cal() {
            result += number;
        }

        private void next(int[] numbers) {
            depth += 1;
            number = numbers[depth];
        }

        private boolean check(int target, int size) {
            if (result == target && depth == size - 1) {
                count++;
                return true;
            }
            if (depth == size - 1) {
                return true;
            }
            return false;
        }
    }


    private void dfs(Info info, int[] numbers, int target) {
        info.cal();
        if (info.check(target, numbers.length)) {
            return;
        }

        info.next(numbers);

        Info plus_temp = new Info(info.number, info.result, info.depth);
        Info minus_temp = new Info(-info.number, info.result, info.depth);


        dfs(plus_temp, numbers, target);
        dfs(minus_temp, numbers, target);
        return;
    }

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

        Info plus_info = new Info(numbers[0], 0, 0);
        Info minus_info = new Info(-numbers[0], 0, 0);
        dfs(plus_info, numbers, target);
        dfs(minus_info, numbers, target);

        return count;
    }
}