프로그래머스/lv2/131701. 연속 부분 수열 합의 개수

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int solution(vector<int> v) {
    int answer = 0;
    int m[500501] = {0,};
    for (int i = 0; i < v.size(); i++)
    {   
        for (int j = 0; j < v.size(); j++) 
        {   
            int s = accumulate(v.begin(), v.begin() + i, 0);
            if (!m[s])
                answer++;
            m[s] = 1; 
            rotate(v.begin(), v.begin() + 1, v.end());
        }
    }
    return answer;
}

길이가 n 까지인 연속 부분 수열까지 구해야 하기 때문에 외부 루프 i엔 vector의 크기만큼 반복하였고, 내부 루프 j엔 길이가 n인 연속 부분 수열의 모든 경우의 수를 찾기 위해 vector의 크기만큼 반복한다.
중복되지 않게 값을 저장하기 위해 메모 할 m이라는 배열을 선언하고, 길이가 i인 연속 부분 수열의 경우의 수는 v.begin()부터 v.begin() + i 까지 합을 구한 뒤 중복되는 값이 아니라면 count를 올린다.
한 칸씩 rotate해주며 모든 경우의 수를 중복되지 않게 검사하며 찾는다.

솔직히 그냥 문제를 보자마자 머릿속에 떠오른 방법은 m이라는 배열을 선언하지 않고 find함수로 중복을 피하며 vector에 추가하고, vector.size()를 리턴해주면 될 것 같았는데 시간복잡도 상으로 너무 비효율적이라 통과하지 못해서 따로 배열을 선언하여 메모하는 방식을 택했다.

현재 프로그래머스로 푼 문제가 320개 쯤 되는데 velog에 올리기엔 하찮은 문제들이 너무 많아서 따로 velog엔 올리지 않았다.

사실 처음엔 올릴 생각도 없었지만 과거로 돌아간다면 하나하나씩 정리해서 올렸을 것 같다.

과거에 풀었던 괜찮은 문제들을 하루에 하나씩 정리해서 올려봐야겠다.

그래도 레벨 2부터는 해결한 즉시 정리하여 블로깅 하는 것이 도움이 될 거라고 생각해서 다시 velog를 켰다.