[Programmers] 연속 부분 수열 합의 개수 c++ (투 포인터, 나머지 계산)

 

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

 

✔ 문제이해

원형으로 수열이 나열되어있다고 할 때, 1부터 수열의 크기만큼 원소들을 더한 결과들의 개수를 중복없이 출력하라.

 

✔ 풀이 + 코드

원형이길래 처음에는 queue로 풀었는데 for문이 세 개나 있고 테스트 케이스 하나만 통과하길래 다른 방법을 생각해보았다.

 

두번째 방법은 똑같은 수열을 그대로 붙히는 방법이었는데, 두 개의 변수를 관리해야 하는 투 포인터의 개념이 어려웠다.

 

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

using namespace std;

int solution(vector<int> elements) {
    set<int> s;
    int len = elements.size();
    vector<int> doubleElements (elements);
    doubleElements.insert(doubleElements.end(), elements.begin(), elements.end());

    for(int i = 0; i < len; i++){
        int sum = doubleElements[i];
        s.insert(sum);
        int idx = 1;
        int end = i;
        while(idx < len){
            idx++;
            end++;
            sum += doubleElements[end];
            s.insert(sum);
        }
    }

    return s.size();
}

 

마지막으로는 굳이 뒤에 붙히지 않아도 나머지 계산으로 할 수 있었을 것 같아서 알게된 풀이이다.

가장 간결하고 이해하기 쉬운 코드인 것 같다. 위의 코드와 효율성의 차이는 없다고 봐도 된다.

 

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

using namespace std;

int solution(vector<int> elements) {
    
    set<int> s;
    int len = elements.size();

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

 

 

✔ 피드백

• 변수 두개를 이용하여 구현하는 방법의 연습이 필요하다.
• 나머지 계산을 잘 활용할 수 있도록 연습이 필요하다.
• 반복문으로 답을 구할 때, 어떤 순서로 답이 나올 수 있는지 다양하게 알아봐야 한다. 반복문 하나를 줄일 수도 있다.

✔ reference

 

투포인터 : https://park-peanut.tistory.com/203

나머지 계산 : 프로그래머스 다른사람의 풀이.