연속 부분 수열 합의 개수

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

입출력 예

elements	result
[7,9,1,1,4]	18

---

문제 해설

단순하게 for문을 3중으로 돌려서 해결할 수 있다.

 

연속하는 부분 수열을 얻기 위해서 1부터 다시 1까지 돌아와야 하기 때문에, 범위끝까지 넘어갔을 경우 다시 첫번째 값으로 돌아오는 함수를 만들어서 사용해야 한다.

 

첫 번째 for문은 탐색해야 하는 수열의 개수를 정하는 for문

두 번째 for문은 전체 수열을 탐색하는 for문

세 번째 for문은 첫번째 for문에서 정해진 개수만큼 중첩으로 더하는 for문

 

이렇게 3개의 for문을 사용하면 된다.

 

중복되는 데이터를 무시하는 방법은 set을 사용하여 해결할 수 있다.

---

첫 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;
int getNum(const vector<int>& elements, int find)
{
    return elements[find % elements.size()];
}
int solution(vector<int> elements) {
    int answer = 0;
    set<int> answerset;
    for(int i = 0; i < elements.size(); i++)
    {
        for(int j = 0; j < elements.size(); j++)
        {
            int now = elements[j];
            for(int k = j; k < j + i; k++) now += getNum(elements, k);
            answerset.insert(now);
        }
    }
    
    return answerset.size();
}

실패

 

순환방식은 옳으나, 첫 번째 값이 두번 탐색되는 경우가 있었다. 세 번째 for문의 k = j부분을 k = j + 1에 k <= j + i 로 수정하면 해결된다.

---

두 번째 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;
int getNum(const vector<int>& elements, int find)
{
    return elements[find % elements.size()];
}

int solution(vector<int> elements) {
    unordered_set<int> answerset;
    for(int i = 0; i < elements.size(); i++)
    {
        for (int j = 0; j < elements.size(); j++)
        {
            int now = elements[j];
            for (int k = j+1; k <= j + i; k++) 
                now += getNum(elements, k);
            answerset.insert(now);
        }
    }
    
    return answerset.size();
}

성공

 

오류를 해결한 뒤 set을 unordered_set으로 고쳐서 조금이나마 데이터 탐색속도를 증가시켰다.