[프로그래머스,Java] Levle2: 연속 부분 수열 합의 개수

 

 

문제분석

 

[7,4,1,1,9] 와같은 배열이 있다면,   중복이 없으며, 연속되는 수의 합의 가짓수를 구하는 문제다.

 

단, 이 문제는 원형의 수열이기때문에,  연속되는 수의 합의 가짓수가 훨씬 많아진다.

 

EX) 첫번째 7과 마지막숫자 9를 선택해도 원형의 배열이니, 연속된숫자의 포함이된다.

 

따라서,  이 원형의 수열임을 가정하고 연속된 숫자를 어떻게 판별하는지가 이 문제의 Key Point다.

 

 

제일 간단한 방법은,

 

기존 배열을 2개 이어서 붙이는것이다.

 

[7,4,1,1,9,7,4,1,1,9] 처럼 말이다. 이러면 원형의 수열까지 판별이 가능하다.

 

단, 이 방법은 매우 간단하지만  배열의 길이가 2배로 늘어나고, 탐색 범위가 매우증가하여, 비효율적이긴하다.

 

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;

        int n=elements.length;

        int[] arr3 = IntStream.concat(IntStream.of(elements), IntStream.of(elements)).toArray();

        Set<Integer> set =new HashSet<>();

        //길이
        for(int i=0;i<n;i++){
            //start
            for(int j=0; j<2*n-i;j++){
                int sum=0;
                //for
                for(int k=0; k<i+1;k++){
                    sum+=arr3[j+k];
                }
                set.add(sum);
            }
        }

        answer=set.size();
        return answer;
    }
}

 

 

또 다른 방법은,

 

기존 배열의   배열의 길이보다 넘어가는 숫자 % 배열의 길이로  원형수열을 구현할수있다.

 

 

import java.util.*;

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

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

        return set.size();
    }
}