[프로그래머스] 연속 부분 수열 합의 개수(Java)

프로그래머스 - 연속 부분 수열 합의 개수

풀이

1. 1개부터 n개까지 더하기 위한 for문 -> size
2. elements의 첫 번째 인덱스부터 마지막 인덱스까지 접근할 for문
3. 각 인덱스 요소부터 size개를 더하는 for문(or 재귀)

대충 이런데 아무생각없이 이거 재귀로 해야하는거 아니야??? 라고 생각하고 재귀로 풀었다,,
근데 생각해보니까 for문으로 못할 거 없는데 왜 재귀로 했지? 싶어서 for문으로도 작성함

재귀 결과

for문 결과

어떤게 더 빠른지 명확하게는 모르겠다
대충 비슷하지 않나 싶음 (그래서 신기)

코드

1. 재귀함수

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] elements) {
		Set<Integer> set = new HashSet<>();
        // 모듈로 연산 사용하기 싫어서 새로운 배열을 만들어서 두 번 붙여줬다
        // ex) elements = {7,9,1,1,4}
        // 	     -> ele = {7,9,1,1,4,7,9,1,1,4}
		int[] ele = Arrays.copyOf(elements, elements.length * 2);
		System.arraycopy(elements, 0, ele, elements.length, elements.length);

		for (int size = 1; size <= elements.length; size++) {
			for (int i = 0; i < elements.length; i++) {
				set.add(getSum(i, 0, ele, size));
			}
		}
		return set.size();
	}

	private int getSum(int i, int num, int[] elements, int size) {
		if (size == 0) return num;
		return getSum(i + 1, num + elements[i], elements, size - 1);
	}
}

2. 반복문

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
		int len = elements.length;

		for (int size = 1; size <= len; size++) {
			for (int i = 0; i < len; i++) {
				int sum = 0;
				for (int j = i; j < i + size; j++) {
					sum += elements[j % len];
				}
				set.add(sum);
			}
		}
		return set.size();
    }
}