타겟 넘버

문제

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

리뷰

• 2021년 8월 12일 총 소요시간 : 1시간 16분 (정답)

  어렵진 않았는데 풀이 할 때 좀 비효율 적이었다.

  • 내 코드

      #include <iostream>
      #include <string>
      #include <vector>
    
      using namespace std;
    
      void init_allNumbers(vector<int> &numbers, vector<int> &edge) {
        int i = 0;
        for (auto num : numbers) {
          edge[i++] = num;  //양수
          edge[i++] = -num; // 음수
        }
      }
    
      void init_adjList(vector<vector<int>> &adjList, vector<int> &edge) {
    
        for (int i = 0; i < edge.size(); i += 2) {
          vector<int> v2;
          v2.push_back(i + 2);
          v2.push_back(i + 3);
    
          adjList.push_back(v2);
          adjList.push_back(v2);
        }
      }
    
      int dfs(vector<int> &edge, int curEdge, vector<vector<int>> &adjList, int sum,
              int &target) {
        int count = 0;
    
        if (curEdge >= adjList.size() - 2) {
    
          sum += edge[curEdge];
    
          if (sum == target)
            return 1;
    
          else
            return 0;
        }
    
        count += dfs(edge, adjList[curEdge][0], adjList, sum + edge[curEdge], target);
        count += dfs(edge, adjList[curEdge][1], adjList, sum + edge[curEdge], target);
    
        return count;
      }
    
      int solution(vector<int> numbers, int target) {
    
        // edge 초기화
        vector<int> edge(numbers.size() * 2, 0);
        init_allNumbers(numbers, edge);
    
        //그래프 초기화
        vector<vector<int>> adjList;
        init_adjList(adjList, edge);
    
        int answer = 0;
    
        answer += dfs(edge, 0, adjList, 0, target);
    
        answer += dfs(edge, 1, adjList, 0, target);
    
        return answer;
      }
    
      int main() {
    
        vector<int> numbers = {1, 1, 1, 1, 1};
    
        int target = 5;
        cout << solution(numbers, target) << endl;
      }

    1. edge의 자가복제

    나는 주어진 number {a,b,c,d...} 에 대해서 edge를 +a , -a 이렇게 두개로 나눠서 edge라는 vector 를 또 만들었는데 굳이 그럴 필요가 있었나 싶다.

    2. vertex의 비효율적인 지정

    edge를 -와 +로 굳이 나눴기 때문에 생겨난 절차. edge가 단일 숫자였다면 무조건 다음 인덱스로 가니까. 밑의 코드처럼 n+1 로 명시할 수 있어서 더 간단했을 거다.

    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);

    모범답안

    정석적인 DFS를 사용했다!

    #include <string>
    #include <vector>
    
    using namespace std;
    
    int total;
    
    void DFS(vector<int> &numbers, int &target,int sum,int n) {
      if(n >= numbers.size()){
          if(sum == target) total++;
          return;
      }
    
      DFS(numbers, target, sum + numbers[n], n+1);
      DFS(numbers, target, sum - numbers[n], n+1);
    }
    
    int solution(vector<int> numbers, int target) {
      int answer = 0;
    
      DFS(numbers, target, numbers[0] , 1);
      DFS(numbers, target, -numbers[0], 1);
    
      answer = total;
    
      return answer;
    }