[코딩테스트] 원형 연속부분수열 합

1. 삼중 for문

int n = elements.size();
    
set<int> s;
    
for(int i=1; i<=n; ++i)
{
    for(int j=0; j<n; ++j)
    {
        int sum =0;
        for(int k=0; k<i; ++k)
        {
            int index = j+k;
            if(index >= n)
            {
                index %= n;
            }
            sum += elements[index];
        }
        s.insert(sum);
    }
}

vector의 원소가 {1, 2, 3, 4, 5}라고 가정을 했을 때 삼중 포문의 로직은 원소가 1개 일 때 → 원소가 2개 일 때 → 원소가 3개 일 때 → ... → 원소가 5개 일 때 처럼 원소의 개수를 순차적으로 체크해 나가는 방식이다. 문제를 풀고 난 후 굉장히 뿌듯해 했지만, 다른 분들의 코드를 참고 해보니 알고리듬에 유연하지 못 한 사고방식으로 구현한 로직이라는 생각이 들었다.

 

2. 이중 for문 **

set<int> s;

int n = elements.size();

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

원소가 { 1, 2, 3, 4, 5 }인 벡터가 있다고 가정했을 때 해당 알고리듬의 로직은 { 1 }, { 1 + 2 }, { 1 + 2 + 3 }, ... { 1 +2 + .. + 5 }, 이후 { 2 }, { 2 + 3 }, ... { 2 + 3 + 4 + 5 + 1 }와 같은 흐름으로 동작한다. 삼중 포문에서는 { 1 }, { 2 }, { 3 }, ... { 5 }, { 1 + 2 } 이런 식이었는데, 너무 틀에 사로잡혔던 사고방식이었던 것 같다.