프로그래머스 | 연속 부분 수열 합의 개수

출처

🌐 코딩테스트 연습 - 연속 부분 수열 합의 개수 | 프로그래머스 스쿨

프로그래머스

 

풀이

1차 풀이

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) 
{
    unordered_set<int> sums;
    
    for(int diff = 0; diff < elements.size(); ++diff)
    {
        for(int i = 0; i < elements.size(); ++i)
        {
            int sum = 0;
            
            for(int j = i; j <= i+diff; j++)
            {
                sum += (j < elements.size())? elements[j] : elements[j - elements.size()];
            }
            
            sums.insert(sum);
        }
    }    
        
    return sums.size();
}

2차 풀이 (dp)

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) 
{
    vector<vector<int>> dp(elements.size(), vector<int>(elements.size()));
    
    for(int i = 0; i < elements.size(); ++i)
    {
        dp[i][0] = elements[i];        
    }

    
    for(int diff = 1; diff < elements.size(); ++diff)
    {
        for(int i = 0; i < elements.size(); ++i)
        {
            dp[i][diff] = dp[i][diff - 1];
            dp[i][diff] += (i + diff < elements.size())? elements[i + diff] : elements[i + diff - elements.size()];
        }
    }    
        
    unordered_set<int> sums;
    for(const vector<int>& sumRow : dp)
    {
        for(const int& s : sumRow)
        {
            sums.insert(s);   
        }
    }

    return sums.size();
}

2차 풀이 리팩토링

    #include <vector>
    #include <unordered_set>

    using namespace std;

    int solution(vector<int> elements) 
    {
        vector<vector<int>> dp(elements.size(), vector<int>(elements.size()));
        unordered_set<int> sums;

        for(int i = 0; i < elements.size(); ++i)
        {
            dp[i][0] = elements[i];
            sums.insert(dp[i][0]);
        }

        for(int diff = 1; diff < elements.size(); ++diff)
        {
            for(int i = 0; i < elements.size(); ++i)
            {
                dp[i][diff] = dp[i][diff - 1];
                dp[i][diff] += (i + diff < elements.size())? elements[i + diff] : elements[i + diff - elements.size()];

                sums.insert(dp[i][diff]);
            }
        }

        return sums.size();
    }

    #include <vector>
    #include <unordered_set>

    using namespace std;

    int solution(vector<int> elements) 
    {
        vector<vector<int>> dp(elements.size(), vector<int>(elements.size()));
        unordered_set<int> sums;

        for(int diff = 0; diff < elements.size(); ++diff)
        {
            for(int i = 0; i < elements.size(); ++i)
            {
                if(diff > 0)
                    dp[i][diff] = dp[i][diff - 1];

                int add = i + diff;
                dp[i][diff] += (add < elements.size())? elements[add] : elements[add - elements.size()];

                sums.insert(dp[i][diff]);
            }
        }

        return sums.size();
    }