[프로그래머스] 연속 부분 수열 합의 개수 C++

문제 설명

---

제한 사항 및 입출력 예제

---

알고리즘 개념

 　예제에서 주어진 원형 수열을 기준으로 연속 부분 수열을 구하면 다음과 같다.

 

 

　따라서 이 합들을 저장할 벡터를 초기화한 후에 중복되는 값을 지워주면 해결된다. 여기서 첫 번째 문제는 연속된 합을 반복문을 이용해 하나 하나 저장하고 비교하려니 시간 초과가 걸린다. 두 번째 문제는 끝이 연결되어 끊기는 부분이 없다는 것이다. 이러한 문제를 해결하기 위해 특정 구간의 합을 구할 수 있는 구간합(Prefix sum) 개념을 이용하여 풀었다.

 

 주어진 예제의 구간합을 표현해보면 다음과 같다.

 

 

　sum이 초기화되는 과정을 보면 다음과 같다.

 

　여기서 구간합은 특정 구간의 합을 구할 수 있다고 했는데, 만약 내가 elements의 인덱스 n부터 k까지의 합을 구하고 싶다면 sum[k + 1] - sum[n]을 해주면 된다. 예를 들어 인덱스 1부터 3까지의 합을 구하고 싶으면 다음 과정에 의해 11이 된다.

 

　이 개념을 통해 연속적인 수의 합을 구하는 방법은 찾았다. 하지만 아직 두 번째 문제가 해결되지 않았는데, 이또한 비교적 간단한 방법으로 해결하였다. 구간합 배열을 기존의 원소에서 한 번 더 확장시켰다. 처음엔 기존 인덱스보다 커지는 경우에 따로 계산해서 구간합 배열을 확장시켰지만, 시간 초과 문제가 걸려서 이러한 방법을 이용하였다.

---

풀이

#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int solution(vector<int> elements)
{
    int size = elements.size();
    vector<int> sum = { 0 };
    vector<int> ans;

    for (int& i : elements)
        sum.push_back(i + sum.back());
    
    for (int& i : elements)
        sum.push_back(i + sum.back());

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
            ans.push_back(sum[i + 1 + j] - sum[j]);
    }

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    return ans.size();
}

※ 함수

#include <numeric>
std::accumulate(v.begin(), v.end(), init) // v의 시작 원소부터 v의 끝점 원소까지 초깃값 init부터 시작해 합을 누적하여 더해 반환한다.

　accumulate()는 쉽게 생각해 배열의 합을 구하는 함수. 

 

#include<algorithm>
v.erase(unique(v.begin(), v.end()), v.end()); // v에서 중복된 원소들의 값을 제거해줌

　erase() 함수와 unique() 함수를 이용하여 벡터 내의 중복된 원소를 제거해줄 수 있다. 유념해야할 점은 unique()함수를 쓰기 전에 배열을 반드시 정렬을 해줘야 한다.