Programmers - 타겟 넘버

---

title: Programmers - 타겟 넘버
date: 2022-07-18
tags:

• Algorithm

---

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

문제 요약

n개의 0 혹은 정수들이 존재한다. 순서는 유지하되, 더하거나 빼기만 하여 타겟 넘버를 만드는 경우의 수를 return한다.

문제 풀이

처음에는 DFS를 생각하였으나, 부분합을 이용한 promising 처리 + 반복적인 재귀 호출이 거슬려서 다른 방식으로 풀었다.
a번째를 기준으로, 이전까지의 결과들을 이용하여 a번째와의 연산을 하면 a번째까지의 결과가 나온다. 이것을 그대로 구현하였다.


unordered_map 2개와 이를 가리키는 포인터를 이용하였다.
처음에는 vector를 사용하려고 하였으나, 두 컨테이너 모두 순회하는 것은 동일하므로 O(1)의 unordered_map이 더욱 나을 것이라 판단하였다.
또한 vector 이용시 같은 a라는 값이 여러 연산을 통해 구해질 때, 기존의 a 값에 추가하거나 새로 뒤에 붙이는 방법이 존재한다.
어떤 방법이라도 예상치 못한 overhead이므로, unordered_map을 이용하였다.
포인터를 통해 두 컨테이너를 바꾸어 가리키며 umpCurrent와 number 연산을 통해 umpNext로 값이 갱신되는 것을 쉽게 이해하도록 프로그램을 작성하였다.

Compare of unordered_map and vector

두 컨테이너의 실제 속도는 결국 각 원소들에 접근하는 속도의 차이이다.
vector는 best와 worst의 속도 차이가 크며 worst의 속도가 상대적으로 매우 크다.
이에 반해 unordered_map은 평균적으로 좋은 성능을 보였으며, 편차 또한 매우 작다.
위에서 언급한 동일한 값이 여러 연산을 통해 구해질 때 생기는 문제로 판단된다.

프로그램 using unordered_map

#include <vector>
#include <unordered_map>

using std :: vector ;
using std :: unordered_map ;

int solution ( vector < int > numbers , int target )
{
    int answer = 0 ;
    unordered_map < int , int > umCurrent ;
    unordered_map < int , int > umNext ;
    int * ipNumber = numbers.data () ;
    int iNumberSize = numbers.size () ;
    unordered_map < int , int > * umpCurrent = & umCurrent ;
    unordered_map < int , int > * umpNext = & umNext ;



    ++ umCurrent [ * ipNumber ] ;
    ++ umCurrent [ * ipNumber * -1 ] ;

    for ( int i = 1 ; i < iNumberSize ; ++i )
    {
        int iNum = * ++ ipNumber ;

        for ( auto iter = ( * umpCurrent ).begin () ; iter != ( * umpCurrent ).end () ; ++ iter )
        {
            ( * umpNext ) [ iter -> first + iNum ] += iter -> second ;
            ( * umpNext ) [ iter -> first - iNum ] += iter -> second ;
        }

        if ( 0 == i % 2 )            // umpCurrent -> umNext
        {
            umNext.clear () ;
            umpCurrent = & umCurrent ;
            umpNext = & umNext ;
        }
        else                        // umpCurrent -> umCurrent
        {
            umCurrent.clear () ;
            umpCurrent = & umNext ;
            umpNext = & umCurrent ;
        }
    }


    return ( * umpCurrent ) [ target ] ;
}

프로그램 using vector

#include <vector>
#include <utility>

using std :: vector ;
using std :: pair ;
using std :: make_pair ;

int solution ( vector < int > numbers , int target )
{
    int answer = 0 ;
    vector < pair < int , int > > vCurrent ;
    vector < pair < int , int > > vNext ;
    int * ipNumber = numbers.data () ;
    int iNumberSize = numbers.size () ;
    vector < pair < int , int > > * vpCurrent = & vCurrent ;
    vector < pair < int , int > > * vpNext = & vNext ;



    vCurrent.emplace_back ( make_pair ( * ipNumber , 1 ) ) ;
    vCurrent.emplace_back ( make_pair ( * ipNumber * -1 , 1 ) ) ;

    for ( int i = 1 ; i < iNumberSize ; ++i )
    {
        int iNum = * ++ ipNumber ;
        int iCurrentSize = ( * vpCurrent ).size () ;

        for ( int j = 0 ; j < iCurrentSize ; ++j )
        {
            pair < int , int > pTemp = ( * vpCurrent ) [ j ] ;
            ( * vpNext ).emplace_back ( make_pair ( pTemp.first + iNum , pTemp.second ) ) ;
            ( * vpNext ).emplace_back ( make_pair ( pTemp.first - iNum , pTemp.second ) ) ;
        }

        if ( 0 == i % 2 )            // vpCurrent -> vNext
        {
            vNext.clear () ;
            vpCurrent = & vCurrent ;
            vpNext = & vNext ;
        }
        else                        // vpCurrent -> vCurrent
        {
            vCurrent.clear () ;
            vpCurrent = & vNext ;
            vpNext = & vCurrent ;
        }
    }

    iNumberSize = ( *vpCurrent ).size () ;
    for ( int i = 0 ; i < iNumberSize ; ++i )
    {
        pair < int , int > pTemp = ( * vpCurrent ) [ i ] ;

        if ( target == pTemp.first )
        {
            answer += pTemp.second ;
        }
    }


    return answer ;
}