연속 부분 수열 합의 개수

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

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();

        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int i = 0; i < elements.length; i++){
            arrayList.add(elements[i]);
            set.add(elements[i]);
        }
        for(int i = 0; i < elements.length; i++){
            arrayList.add(elements[i]);
        }

        for(int i = 2; i <= elements.length; i++){
            int startIdx = 0;
            while (true){
                int temp = 0;
                for(int j = startIdx; j < startIdx + i; j++){
                    temp += arrayList.get(j);
                }
                set.add(temp);
                startIdx++;
                if(startIdx % elements.length == 0) break;
            }
        }
        return set.size();
    }
}

무식한 방법의 첫풀이.
처음에 받은 배열 그냥 쭉 이어붙여서 원형이라고 치고 개수만큼 더해주면서 Set 에 넣어줌으로써 중복도 방지한다.

속도는 당연히 느리지.. 반복문과 while 문을 계속 도니까.

import java.util.*;

class Solution {
        public int solution(int[] elements) {
            Set<Integer> set = new HashSet<>();
            int[] dp = new int[elements.length];
            for(int len = 1;len <= elements.length; len++){
                for(int i = 0;i<elements.length;i++){
                    dp[i] += elements[(len+i-1)%elements.length];
                    set.add(dp[i]);
                }
            }
            return set.size();
        }
    }

DP 를 이용한 다른사람의 풀이.

dp[i] += elements[(len+i-1)%elements.length];

굳이 배열을 확장안하고 % 를 통해 인덱스를 넘어갈수있게해준다. 내 생각은 여기까진 갔는데 dp 까지는..

아름다운 속도의 차이가 난다.