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

문제

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

---

풀이(15분)

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        Set<Integer> set = new HashSet<>();
        int originLength = elements.length;
        int[] arr = new int[originLength * 2 - 1];
        for(int i = 0; i < originLength - 1; i++){
            arr[i] = elements[i];
            arr[i+originLength] = elements[i];
        }
        arr[originLength-1] = elements[originLength-1];

        for(int i = 0; i < originLength; i++){
            int sum = 0;
            for(int j =0; j < originLength; j++){
                sum += arr[i + j];
                set.add(sum);
            }
        }
        answer = set.size();
        return answer;
    }
}

 

원형수열을 사용해야 하기 때문에 x2-1의 길이만큼의 배열을 만들어준다.

예를 들어 문제에서 제시된 7 9 1 1 4라면 9의 길이만큼의 배열을 만들어 7 9 1 1 4 7 9 1 1과 같이 만들어주는 것이다.

 

그 후 4까지 각각의 자리에서

자기 자신만을 합으로 사용했을 때 (1개의 합) 부터 4 7 9 1 1 즉 originLength - 1 만큼의 추가적인 수열을 합쳤을 때의 경우를 모두 계산해 준다.

 

물론 중복되는 연산이 많을 수 있다는 단점이 있지만 배열 길이의 특성을 보면 문제가 없을 것이라고 판단했다.

 

Set 자료구조를 통해 중복을 제외하고 정답을 출력한다.