[Lv.2]연속 부분 수열 합의 개수

각각의 elements 원소를 한자리, 두자리, 세자리....elements.length까지 중복없이 더한 결과값의 갯수를 구하여야 한다.

처음에 원형수열을 이용하여풀고자, elements * 2한 배열을 하나 더 만드려고 했었다. 그러나 좀 생각해보니 elements를 있는 그대로 활용할 수 있었다. 각각의 elements원소에 자신의 다음에 올 수를 반복문을 통해 더해주면, 한자리, 두자리, 세자리 ... length까지 값을 모두 더할 수 있었다. 처음 설계한 방법은 List를 만들어 따로 결과값들을 저장해주었다. if 문을 사용하여, 이미 숫자가 있으면 add하지 않게끔 하였다. 이 방법을 사용하였더니, 시간초과가 뜨게되었다. 그래서 중복을 허용하지 않는 set 자료구조를 사용하여 풀이하였고, 시간초과가 뜨지않고 통과하였다.

아래의 코드는 프로그래머스에서 무사히 통과한 코드이다. 그 아래의 코드는 내가 처음 설계하고 구현한, 시간초과가 뜬 코드이다. 

package Lv_2;

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

public class 연속부분수열합의개수 {
    public static int solution(int[] elements) {
        int answer = 0;
        Set<Integer> sum_list = new HashSet<>();
        int[] ele_sum = new int[elements.length];
        int n = 0;
        for (int i = 0; i < elements.length; i++) {
            for (int j = 0; j < elements.length; j++) {
                ele_sum[i] += elements[(j+n)%elements.length];
                sum_list.add(ele_sum[i]);
            }
            n++;
        }
        answer = sum_list.size();
        return answer;
    }

    public static void main(String[] args) {
        int[] elements = {7, 9, 1, 1, 4};
        int result = solution(elements);
        System.out.println("결과는 = " + result);
    }
}

시간초과 코드

package Lv_2;

import java.util.ArrayList;
import java.util.List;

public class 연속부분수열합의개수 {
    public static int solution(int[] elements) {
        int answer = 0;
        List<Integer> sum_list = new ArrayList<>();
        int[] ele_sum = new int[elements.length];
        int n = 0;
        for (int i = 0; i < elements.length; i++) {
            for (int j = 0; j < elements.length; j++) {
                ele_sum[i] += elements[(j+n)%elements.length];
                if (!sum_list.contains(ele_sum[i])) {
                    sum_list.add(ele_sum[i]);
                }
            }
            n++;
        }
        answer = sum_list.size();
        return answer;
    }

    public static void main(String[] args) {
        int[] elements = {7, 9, 1, 1, 4};
        int result = solution(elements);
        System.out.println("결과는 = " + result);
    }
}