프로그래머스/Lv.2

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

MINU.SHINNNN 2023. 5. 27. 12:08

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

원형 수열에서 연속 부분 수열 합의 개수를 구해야 하는 문제입니다. 단 중복이 없어야 합니다.

즉, 임의 시작 원소부터 시작해, 최대 elements 변수 크기를 가지는 부분수열의 합을 중복없이 카운트 하는 문제입니다.

 

two-pointer 알고리즘을 사용하면 left, right 포인터를 조절하여 원하는 부분수열의 크기만큼 합을 구할 수 있습니다. 하지만 right 포인터의 경우 다시 elements 의 가장 처음을 가리켜야 하기 때문에, elements 변수를 원형수열을 나타내는 벡터로 수정해야 합니다.

 

따라서 

1. 주어진 elements 로 원형 수열 만들기 -> 예시의 7 9 1 1 4 벡터뒤에 다시 7 9 1 1 4 를 붙이면 7 9 1 1 4 7 9 1 1 4 가 됩니다. 따라서, left 포인터가 굵게 표시된 4를 가리킬때 right 포인터는 처음으로 돌아가지 않고 left 뒤의 원소인 7부터 다시 가리킬 수 있습니다.

2. 위 개념을 사용하여, 원소가 1개일 때부터 elements 벡터의 원래 개수 만큼까지의 부분 수열을 계속해서 만들어줍니다.

3. 부분 수열의 개수는 cnt 변수를 사용해 카운트 합니다.

4. right 변수는 left 바로 다음 원소를 가리키도록 left+1 로 초기화 하고, sum 변수에 계속해서 더해나갑니다. 

5. sum 변수는 중복을 방지하는 set 자료 구조를 사용해 저장합니다.

6. 최종적으로, 모든 임의 시작점에서 부분 수열의 개수가 1, 2, 3 ... elements.size() 개일 때의 합을 구해 s 변수에 저장하면 답을 구할 수 있습니다.

 

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

using namespace std;

set<int> s;

int solution(vector<int> elements) {
    int answer = 0;
    int len = elements.size();
    // 원형수열 만들기
    for (int i=0; i<len; i++) { elements.push_back(elements[i]); }
    
    // left, right 포인터 사용하여 1~len 개수의 부분 수열 만들기
    for (int left=0; left<len; left++) {
        // 부분수열 원소 1개
        int sum = elements[left];
        s.insert(sum);
        // 부분수열 원소 2개 이상
        int cnt = 1; // 부분 수열의 원소 수 count
        int right = left+1;
        while (cnt < len) {
            sum += elements[right];
            s.insert(sum);
            cnt += 1;  
            right += 1;    
        }
    }
    
    answer = s.size();
    return answer;
}