링버퍼 구현과 링버퍼 순회에 대한 내용

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

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

제한사항
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
입출력 예
elements result
[7,9,1,1,4] 18
입출력 예 설명
입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

---

풀이

C

#include <stdio.h>
#include <stdbool.h>

#define MAX_SUM 1000001 // 가능한 부분 수열 합의 최대 값

// 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수의 개수를 반환하는 함수
int solution(int elements[], int n) {
    // 누적 합 배열
    bool possible[MAX_SUM] = {0};

    // 누적 합 계산
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i; j < i + n; ++j) {
            sum += elements[j % n]; // 연속하는 부분 수열의 합 계산
            possible[sum] = true; // 가능한 합 저장
        }
    }

    // 중복을 제외한 가능한 부분 수열 합의 개수 카운트
    int count = 0;
    for (int i = 1; i < MAX_SUM; ++i) {
        if (possible[i]) count++;
    }

    return count;
}

C ++

#include <vector>
#include <unordered_set>

using namespace std;

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

    // 부분 수열의 합 계산
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i; j < i + n; ++j) {
            sum += elements[j % n];
            possibleSums.insert(sum);
        }
    }

    return possibleSums.size();
}

부분수열이라는 것은 원 수열의 크기를 넘어 설수 없다 그래서 다음과 같이 반복문을 수행한다
int j = i; j < i + n; ++j

---

배운 것들

링버퍼를 간단하게 구현하기

링버퍼는 끝에 도달해도 처음으로 돌아가는 특성을 가지고 있어서 순서대로 뽑을때
인덱스 [0]~[n] 그리고 [n] ,[0], [1] ... 이런 식으로 한번 배열 끝까지 순회
다시 처음으로 돌아가야한다 해야한다는 개념을 바탕으로 링버퍼를 순회하는 부분이 다음과 같다

 for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i; j < i + n; ++j) {
            sum += elements[j % n]; // 연속하는 부분 수열의 합 계산
            possible[sum] = true; // 가능한 합 저장
        }
    }

sum += elements[j % n]; 이부분을 이용하여 최대 배열을 넘은 j를 배열을 크기인 n으로 나눈 나머지를 인덱스로 사용하면서 계속 링버퍼를 순회하도록 한 것임

중복 제거

C언어를 사용하는 경우 중복을 방지 하기위해서 bool 타입으로 배열을 선언하고
조건에 맞을 경우 해당 인덱스의 요소를 true로 변환 시키는 방식을 사용 함


하지만 C++ 에는

#include <unordered_set>
  unordered_set<int> possibleSums;

unordered_set이라는 자료구조를 사용하여 중복을 방지함
unordered_set은 내부적으로 해시 테이블을 사용하여 원소들을 저장하므로, 각 원소에 대해 해시값을 계산하여 저장함