[프로그래머스/C++, C#] 타겟 넘버

타겟 넘버

---

 

 

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

프로그래머스

 

 

 

 

 

그래프 탐색 문제

DFS, BFS 둘 다 가능

 

 

코드

---

 

(1) DFS

 

 

-C++

#include <string>
#include <vector>

using namespace std;

int target_num;
int result;
vector<int> input_numbers;

void DFS(int idx, int num){
    if(idx==input_numbers.size()){
        if(num==target_num){
            result++;
        }
        return;
    }
    int num1=num+input_numbers[idx];
    int num2=num-input_numbers[idx];
    DFS(idx+1, num1);
    DFS(idx+1, num2);
}

int solution(vector<int> numbers, int target) {
    target_num=target;
    input_numbers=numbers;
    int answer = 0;
    DFS(0, 0);
    answer=result;
    return answer;
}

 

 

-C#

using System;

public class Solution {
    int[] numbers = new int[20];
    int target;
    int answer;
    int length;
    
    public int solution(int[] numbers, int target) {
        this.numbers=numbers;
        this.target=target;
        this.length=numbers.Length;
        int answer = 0;
        DFS(0,0);
        answer=this.answer;
        return answer;
    }
    
    private void DFS(int idx, int num){
        if(idx==this.length){
            if(num==this.target){
                this.answer++;
            }
            return;
        }
        int num1=num+this.numbers[idx];
        int num2=num-this.numbers[idx];
        DFS(idx+1, num1);
        DFS(idx+1, num2);
    }
}

 

 

 

 

(2)BFS

 

 

-C++

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(numbers[0], 0));
    q.push(make_pair(-numbers[0], 0));
    while(!q.empty()){
        int num = q.front().first;
        int idx = q.front().second;
        q.pop();
        if(idx==numbers.size()-1){
            if(num==target)
                answer++;
            continue;
        }
        q.push(make_pair(num+numbers[idx+1], idx+1));
        q.push(make_pair(num-numbers[idx+1], idx+1));
    }
    return answer;
}

 

 

-C#

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>();
        q.Enqueue(new Tuple<int, int>(numbers[0], 1));
        q.Enqueue(new Tuple<int, int>(-numbers[0], 1));
        while(q.Count>0){
            Tuple<int, int> temp = q.Dequeue();
            int num=temp.Item1;
            int idx=temp.Item2;
            if(idx==numbers.Length){
                if(num==target)
                    answer++;
                continue;
            }
            q.Enqueue(new Tuple<int, int>(num+numbers[idx], idx+1));
            q.Enqueue(new Tuple<int, int>(num-numbers[idx], idx+1));
        }
        return answer;
    }
}

 

 

 

 

풀이

---

시작지점을 0으로 두어 주어진 숫자들을 + 혹은 - 연산하여 나온 수를 그 버텍스에 인접한 버텍스로 생각하면 된다.

[1, 1, 1, 1, 1]이 주어진 경우에서 0이 시작 버텍스라 하였을 때 다음 버텍스는 0에 +1한 +1과 -1한 -1 두 숫자가 인접한 버텍스가 되는 것이다.

+1 버텍스에서 인접한 버텍스는 +1을 한 +2, -1을 한 0이 되는 것이며, -1 버텍스에서 인접한 버텍스는 +1을 한 0,  -1을 한 -2가 인접한 버텍스가 된다.

그렇게 계속 이어가다 마지막 버텍스에서의 숫자가 주어진 숫자와 같은지를 확인하면 된다.(같으면 answer++)

 

 

버텍스의 값이 몇 번의 연산을 거쳐 나온 것인지도 알아야 하므로 DFS의 경우 매개변수로 접근해야 할 인덱스 번호와 현재 연산결과를 두었고, BFS의 경우 queue 값으로 현재 연산결과와 접근해야 할 인덱스(혹은 이전 인덱스)를 저장하였다.

 

 

dfs

 

 

bfs

 

 

 

 

다른 사람 코드

---

 

다른예시 1

using System;

public class Solution {
    static int Dfs(int[] arr, int target, int idx, int num)
    {
        if (idx == arr.Length)
        {
            if (target == num) return 1;
            else return 0;
        }
        else
            return Dfs(arr, target, idx + 1, num + arr[idx]) + Dfs(arr, target, idx + 1, num - arr[idx]);
    }

    public int solution(int[] numbers, int target) {
        int answer = 0;
        return Dfs(numbers, target, 0, 0);
    }
}

 

 

DFS에 반환형을 두어 바로 구하는 방법도 있었다.

값을 +한 DFS의 반환값과 값을 -한 DFS의 반환값을 더하는 형식이다.

target==num(계산을 끝까지 진행했을 때 타겟과 값이 같을 경우)일 경우 return 1, 그렇지 않을 경우 return 0인데 이런 식으로 전체 경우가 나오면 이 숫자들을 다 더하는 식인 것이다.

 

 

 

 

---

 

다른예시 2

 

using System;

public class Solution {
    public int solution(int[] numbers, int target)
        {
            int answer = 0;

            for(int i = 0; i < Math.Pow(2,numbers.Length); i++)
            {
                int sum = 0;
                int temp = i;

                for (int j = 0; j < numbers.Length; j++)
                {
                    if(temp % 2 == 1)
                    {
                        sum -= numbers[j];
                        temp--;
                    }
                    else
                    {
                        sum += numbers[j];
                    }
                    temp /= 2;
                }

                if(sum == target)
                {
                    answer++;
                }
            }

            return answer;
        }
}

 

 

이중 for문을 사용하여 전체 경우를 탐색하는 방법이다.(그래프 탐색은 아님)

버텍스 하나 당 2가지 경우가 생기므로 바깥쪽 for문은 2를 주어진 수의 갯수만큼 곱한만큼 돌리도록 되어있다.

변수 temp를 두어 다음 연산의 부호를 결정하도록 구현되어있다.

(temp 구현 방식은 아직 잘 모르겠,,,, 연산부호 결정하는 건 알겠다만 그러기 위해 나온 코드를 이해 못하였,,,,)