[Programmers] Lv2. 연속 부분 수열 합의 개수 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

중복없이 저장을 해야 하니, set에 저장하였습니다. 연속 수열 합계를 구하는 부분에선 deque를 활용하여 풀었습니다. 인덱싱이 가능하고, 맨 앞 맨 뒤 삽입 삭제가 효율적인 deque라면 좋은 효율을 낼 것 같다고 생각하였습니다.

알고리즘은 다음과 같습니다.

 

1. vector에 저장되어 있던 elements의 원소들을 모조리 deque로 옮겨 저장합니다.

2. 0번 인덱스부터 추출할 개수 (1 ~ element.size()) 인덱스만큼의 합계를 구합니다.

    - 합계를 set에 저장합니다.

    - deque의 맨 앞 원소를 맨 뒤로 보냅니다.

    - deque의 원소의 개수만큼 반복합니다.

 

 

위 예제를 예로 들면, [7, 9, 1, 1, 4]에서 연속 부분 수열 길이가 2인 것을 만든다고 하였을 때,

#1
7 9 1 1 4
// 7 + 9 = 16  -> set에 저장
// 7은 맨 뒤로 보냄

#2
9 1 1 4 7
// 9 + 1 = 10  -> set에 저장
// 9는 맨 뒤로 보냄

...


#5
4 7 9 1 1
// 4 + 7 = 11  -> set에 저장
// 4는 맨 뒤로 보냄  -> 7 9 1 1 4로 원래대로 돌아옴 -> 루프 끝

 

✏️소스 코드 및 결과

#include <set>
#include <deque>
#include <vector>
using namespace std;


int Sum(const deque<int>& myDeque, int selection) {
    int sum = 0;
 
    for (int i = 0; i < selection; i++)
        sum += myDeque[i];
    return sum;
}

deque<int> MigrationToDeque(const vector<int>& elements) {
    deque<int> result(elements.size());

    for (int i = 0; i < result.size(); i++)
        result[i] = elements[i];
    return result;
}

int solution(vector<int> elements) {
    deque<int> myDeque = MigrationToDeque(elements);
    set<int> answers;

    for (int selection = 1; selection < myDeque.size(); selection++) {
        for (int start = 0; start < myDeque.size(); start++) {
            int sum = Sum(myDeque, selection);
            answers.insert(sum);
            
            int front = myDeque.front();
            myDeque.push_back(front);
            myDeque.pop_front();
        }
    }

    int sum = Sum(myDeque, myDeque.size());      // 전부 선택하는 것은 바꿔가며 해도 값이 똑같으므로 한 번만 수행
    answers.insert(sum);
    return answers.size();
}