CS/알고리즘

[프로그래머스] 타겟 넘버

infitry 2022. 6. 18. 11:06
반응형

해당 문제를 풀려면 DFS (깊이우선탐색) / BFS (넓이우선탐색)에 대한 이해가 필요하다.

 

그림 1

 

그림에서 보다시피 DFS는 한 쪽으로 먼저 끝까지 탐색하고, BFS는 현재 위치에서 접근가능한 모든 노드(경우의 수)를 탐색 한 후

다음 Depth로 넘어간다.

 

DFS

    - 재귀 또는 스택으로 구현 가능하다.
    - 깊게 탐색하는 것
    - 어떤 노드를 방문하였는지에 여부를 반드시 검사해야한다.
    - 모든 노드를 방문하고자 할 때, 이 방법을 사용한다.
    - BFS에 비하여 간단하다.
    - BFS에 비하여 느리다.

    - 이동 과정에서 제약이 있을 경우 DFS를 사용하는 것이 유리

BFS

    - 재귀동작 X

    - 선입선출을 원칙으로 함 (FIFO)

    - 넓게 탐색하는 것
    - 어떤 노드를 방문하였는지 여부를 반드시 검사 할 것
    - 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용

    - 최단 거리를 구해야 하는 경우 BFS가 유리

 

 

문제 - 타겟 넘버

문제 설명

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 이하인 자연수입니다.
입출력 예numberstargetreturn
[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 합니다.

 

문제를 파악해보면 0부터 시작하여 numbers의 각 항목을 거칠 때마다 2가지의 경우의 수가 생긴다. (+ 혹은 - 를 계산한 이진트리가 생김)

DFS로 풀면, 재귀로 numbers의 마지막 항목을 처리할 때 까지 DFS 메소드를 호출하면 되고,

BFS로 풀면 현재 노드를 큐에서 꺼내고, 현재 위치에서 접근 가능한 노드들을 계산하여 큐에 다시 넣고 마지막 항목을 처리할 때까지 반복한다.

 

BFS 풀이

class Node {
    public Node (int offset, int value) {
        this.offset = offset;
        this.value = value;
    }

    private int offset;
    private int value;
}

public int bfs(int[] numbers, int target) {
    Queue<Node> q = new LinkedList<>();
    int answer = 0;
    q.offer(new Node(0, 0));    // 큐에 첫 번째 요소를 적재함.

    while (!q.isEmpty()) {
        Node node = q.poll();
        int value = node.value;
        int offset = node.offset;
        if (offset == numbers.length) {
            if (value == target) {
                answer++;
            }
            continue;
        }

        q.offer(new Node(offset + 1, value - numbers[offset]));
        q.offer(new Node(offset + 1, value + numbers[offset]));
    }

    return answer;
}

DFS 풀이

public int dfs(int[] numbers, int depth, int target, int sum) {
    if (depth == numbers.length) { // 마지막 노드까지 탐색한 경우
        if (target == sum) {
            return 1;
        }
        return 0;
    }
    // 재귀로 + 되는 경우와 - 되는 경우를 깊이 탐색한다.
    return dfs(numbers, depth + 1, target, sum + numbers[depth]) + dfs(numbers, depth + 1, target, sum - numbers[depth]);
}
반응형