코딩테스트 --연속 부분 수열 합의 개수- (프로그래머스 / C++)

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

프로그래머스

 

 

문제!

---

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

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

---

원형의 숫자들로 부분 숫자열을 만들어 만들수 있는 모든 숫자열의 갯수를 출력하는 문제입니다.

 

 

문제는 굉장히 쉬운데 제가 어렵게 풀어버렸네요....

 

 

일단 쉬운 풀이부터!

 

 

 

시작!

---

첫번째 풀이방식은 순서대로 더해주며 모든경우를 탐색하는 방법입니다.

 

먼저 중복 제거를 위한  set 을 선언해주고

set<int> S;

 

 

모든 경우에 대해서 i번째부터 1개 선택 ~ n개 선택 까지 해주는  방식! 

 for (int i = 0 ; i < elements.size() ; ++i) {
        int sum = 0;
        for (int j = i ; j < i + elements.size() ; ++j) {
            sum += elements[j % elements.size()];
            S.insert(sum);
        }
    }

 

 

바로 s의 사이즈를 출력해주면 끝;;

 

 

 

 

 

---

그리고 다음 두번째 방법은 코드가 좀 길긴하지만 좀더 빠른 방식!

 

바로 누적합을 사용하는 방법입니다...

 

먼저 아래처럼 선언해주고 

현재 원형 숫자를 2배로 늘려줍시다(이부분을 %연산으로 줄일수도 있겠네요!)

int answer = 0;
    int sum_ma=0;
    int memo=0;
    vector<int>answer_list;
    vector<int>twi_elements=elements;

    
    for(int i=0;i<elements.size();i++){// 한번 더 넣어주면서 최댓값 보기
        twi_elements.push_back(elements[i]);
        sum_ma+=elements[i];
    }

    vector<int>list(twi_elements.size(),0);

    for(int i=0;i<twi_elements.size();i++){// 누적합
        list[i]=list[i-1]+twi_elements[i];
    }

 

그리고 누적합 연산을 해준뒤

 

 

모든 합을 리스트에 넣어 줍시다.

for(int i=0;i<twi_elements.size();i++){
        for(int j=i+1;j<twi_elements.size();j++){//i+1 ~ j
            memo=list[j]-list[i];

            if(memo>sum_ma){
                break;
            }
            answer_list.push_back(memo);

        }
    }

 

 

그 다음은 벡터의 중복제거 방식으로 제거해줍니다.

    sort(answer_list.begin(),answer_list.end());


    answer_list.erase(unique(answer_list.begin(),answer_list.end()),answer_list.end());

 

첫번째 방식과 마찬가지로 answer리스트의 사이즈를 출력하면 끝...

 

 

 

속도는 확실히 빠릅니다....

대신 코드가 기네요!

 

두 방법중 선택해서 풀어주시면 될 것 같습니다!

 

 

끝!

 

 

ALL1

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

using namespace std;

int solution(vector<int> elements) {
    set<int> S;

    for (int i = 0 ; i < elements.size() ; ++i) {
        int sum = 0;
        for (int j = i ; j < i + elements.size() ; ++j) {
            sum += elements[j % elements.size()];
            S.insert(sum);
        }
    }

    return S.size();
}

 

 

ALL2

#include <string>
#include <vector>
#include <algorithm>

#include <iostream>
using namespace std;


int solution(vector<int> elements) {
    int answer = 0;
    int sum_ma=0;
    int memo=0;
    vector<int>answer_list;
    vector<int>twi_elements=elements;

    
    for(int i=0;i<elements.size();i++){// 한번 더 넣어주면서 최댓값 보기
        twi_elements.push_back(elements[i]);
        sum_ma+=elements[i];
    }

    vector<int>list(twi_elements.size(),0);

    for(int i=0;i<twi_elements.size();i++){// 누적합
        list[i]=list[i-1]+twi_elements[i];
    }


    for(int i=0;i<twi_elements.size();i++){
        for(int j=i+1;j<twi_elements.size();j++){//i+1 ~ j
            memo=list[j]-list[i];

            if(memo>sum_ma){
                break;
            }
            answer_list.push_back(memo);
        }
    }

    sort(answer_list.begin(),answer_list.end());


    answer_list.erase(unique(answer_list.begin(),answer_list.end()),answer_list.end());

    return answer_list.size();
}

 

 

 

틀린점이 있다면 댓 달아주세요!