[programmers] 연속 부분 수열 합의 개수

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

원형 수열이 되도록 수열을 두 번 반복하기.

index를 0~len-1까지 증가시키면서 sum을 구하는데, 그 길이를 1~len까지 늘리기. (sliding window?)

set에 이 합들을 저장해 중복되지 않는 개수를 구하기.

 

---------------------------------------------------풀이----------------------------------------------------

 

원형 수열에서 원하는 길이를 찾아야하므로, 주어진 수열을 한 번 더 반복해 붙여준다.

즉, 1 2 3 4 5이면 1 2 3 4 5 1 2 3 4 5 이런식으로 만들어준다.

그리고 여기서 0~len-1까지를 시작 인덱스로 잡아주면 원형 수열에서의 연속 부분 수열의 값을 찾을 수 있다.

 

시작 인덱스에 대해서 sliding window처럼 사용하는데, 이 길이를 1~len까지 변화시킨다.

그 합을 각각 구해주고, set에 저장한다.

set은 중복되지 않은 값만 저장할 수 있으므로 unique한 값들이 저장된다.

따라서 set의 개수를 리턴하면 합의 종류를 모두 리턴할 수 있다.

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

using namespace std;

// 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수의 종류=?
int solution(vector<int> elements) {
    int answer = 0;
    int len = elements.size();
    // 원형이므로 뒤에 한 번 더 반복해 이어붙여주기
    for(int i = 0; i < len; i++){
        elements.push_back(elements[i]);
    }
    
    // 합들을 저장할 set
    set<int> s;
    
    // 연속 부분 수열의 합 구하기
    for(int i = 0; i < len; i++){
        int sum = 0;
        // i~i+j까지의 합
        for(int j = 0; j < len; j++){
            sum += elements[i+j];
            s.insert(sum);
        }
    }
    
    answer = s.size();
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

부분 수열을 단순하게 구해봤는데 통과가 된다.

더 효율적인 방법이 없을지 고민해 보는게 좋을 것 같다.