연속 부분 수열 합의 개수 / 모듈러 연산으로 vector size 초과 피하기

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

 

처음에 재귀호출로 풀었다가 연속된 부분 수열이 아니라 모든 경우의 수를 다 더해서 결과 값이 큰 값이 나왔었다.
"연속 부분 수열" 이라는 말을 망각했던 것.. 이후 다시 다른 방법을 찾았다.

우선 합산 결과가 중복되지 않아야하기 때문에 set을 선택했고, 순서는 상관 없기에 unordered_set을 사용하기로 최종 결정했다.

모든 요소가 합산의 시작점이 될 수 있기에 배열의 첫요소를 바꾸기 위해, 양쪽 끝 요소의 삽입/삭제가 빠른 deque를 사용해서 element의 데이터를 저장해주었다.
이러한 방식으로 "구현 코드 1번"을 작성하였는데, 타인 코드를 보니 "모듈러 연산"으로 직접 배열의 순서를 바꾸지 않고 배열의 끝요소에서 다시 첫번째 요소의 값을 가져오는 것을 확인했다.

예전에도 이 방법으로 접근했던 적이 있는데, 막상 문제를 풀려고 하면 매번 생각이 안난다..
아무튼 이 모듈러 연산으로 접근하는 방향의 코드가 "구현 코드 2번"이다.

 

✅ 구현 코드 1번 (unordered_set / deque / accumulate)

#include <string>
#include <vector>
#include <unordered_set>
#include <deque>
#include <numeric> // accumulate

using namespace std;

int solution(vector<int> elements)
{
    // 합산 결과를 키로 저장. 중복 x
    unordered_set<int> us;

    // 원형 순열로 모든 요소가 합산의 시작점이 될 수 있다.
    // 양쪽 끝에서의 삽입/삭제가 빠른 deque 컨테이너 사용.
    deque<int> dq(elements.begin(), elements.end());
    
    // 더할 숫자 개수
    int cnt = 1;
    while (cnt != elements.size())
    {
        // elements의 크기만큼 반복
        // 원형 순열이기에 덧셈 시작 위치를 모든 요소에 적용
        for (int i = 0; i < elements.size(); ++i)
        {
            // dq의 시작부터 cnt 개수만큼 더한 값을 set에 저장
            us.insert(accumulate(dq.begin(), dq.begin() + cnt, 0));

            // 원형 순열이기 때문에 dq.front 시작점 갱신
            int temp = dq.front();
            dq.pop_front();
            dq.push_back(temp);
        }
        // 더할 갯수 증가
        cnt++;
    }
    
    // 모든 요소를 더할 때는 시작점이 중요하지 않기에 한 번만 저장
    us.insert(accumulate(dq.begin(), dq.begin() + cnt, 0));
    
    // set의 크기가 곧 합산의 경우의 수
    int answer = us.size();
    return answer;
}

 

 

✅ 구현 코드 (unordered_set / 모듈러 연산)

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) 
{
    unordered_set<int> us;
    int size = elements.size();

    for (int start = 0; start < size; ++start)
    {
        int sum = 0;
        for (int current = start; current < start + size; ++current)
        {
            // 모듈러 연산을 통해 vector size 범위 초과하지 않도록 함.
            // current가 vector size 값이 되면 0번 인덱스가 된다.
            sum += elements[current % size];
            us.insert(sum);
        }
    }

    int answer = us.size();
    return answer;
}

🟢 모듈러 연산으로 접근했을 때의 장점:

• 따로 deque와 같은 컨테이너를 추가로 사용하지 않아, 추가적인 메모리 할당과 연산 작업이 없어 시간복잡도와 공간복잡도 성능이 증가
• 각 시작 요소부터 최대 합산 개수까지 int 변수에 더해가며 바로 set에 등록하기 때문에 accumulate도 사용하지 않아도 되어 시간복잡도 성능 증가
• 코드 가독성면에서도 간결함