[Programmers]#Level2_연속 부분 수열 합의 개수, 투 포인터 알고리즘, set 컨테이너

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 투 포인터 알고리즘

[알고리즘]#7_투 포인터

 

[정의] : 투 포인터 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분 배열을 찾는 알고리즘입니다.

[특징] : 투 포인터 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다.

[동작 방식]

1. 배열의 시작 위치를 가리키는 포인터, 배열의 마지막 위치를 가리키는 포인터, 두 개의 포인터를 초기화
2. 두 포인터가 움직이며, 주어진 조건을 만족하는 부분 배열을 찾습니다.
3. 조건을 만족할 경우, 원하는 동작을 수행하고 마칩니다.
4. 조건을 만족하지 못할 경우, 두 포인터의 위치 변경을 시도합니다.
5. 원하는 해를 얻을 때까지, 2~4번 동작을 반복합니다. 

 

2. set 컨테이너

[Basic C++] #29_Set, STL 컨테이너

 

[정의] : C++의 STL에서 제공하는 set 컨테이너는 중복을 허용하지 않고, 정렬된 상태를 유지하는 노드 기반의 연관 컨테이너입니다. set 컨테이너는 Key 값을 원소로 이루어진 집합입니다.

[특징] : set 컨테이너는 균형 이진트리로 구현되어, 내부적으로 정렬된 상태를 유지합니다.

[성능] : set 컨테이너의 탐색/삽입/삭제 연산의 최악 시간 복잡도는 O(log n)입니다.

 

3. Mod 연산으로 right 포인터의 위치를 설정하자!

 

1. 배열의 시작 위치를 가리키는 포인터, 이를 기준으로 +1 씩 점점 증가하는 포인터를 통해 투 포인터 알고리즘을 시작합니다.
2. 두 포인터가 가리키는 위치 사이에 존재하는 항목들의 누적 합을 계산하여 set 컨테이너에 삽입하고, 시작 위치를 가리키던 포인터와 부분 배열의 마지막 위치를 가리키던 포인터를 1씩 증가시키며 시작 위치를 가리키던 포인터가 배열의 끝 위치에 도달할 때까지 알고리즘을 수행합니다.

 

---

 

#3. 코드

 

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

using namespace std;

int solution(vector<int> elements)
{

    set<int> s;

    for (int i = 1; i <= (int)elements.size(); ++i)
    {
        // 최소 연속 부분 수열 개수 = 1
        int left = 0;
        // 최대 연속 부분 수열 개수 = elements.size()
        int right = left + i;

        // 왼쪽 경계가 배열의 마지막 원소를 가리킬 때 까지 진행
        while (left < elements.size())
        {
            int sum = 0;
            for (int j = left; j < right; ++j)
            {
                sum += elements[(j % (int)elements.size())];
            }
            // set 컨테이너에 삽입(중복 불가)
            s.insert(sum);

            left++;
            right++;
        }
    }

    return s.size();
}

 

---