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

문제

연속 부분 수열 합의 개수

📌 아이디어

해당 문제는 기존의 주어진 배열을 2배로 늘려 탐색을 진행했습니다. 또한, HashSet 자료 구조를 활용해 중복값을 배제하도록 했습니다.

1. 주어진 배열을 리스트로 변환해 2배의 형태로 만듭니다.
2. 기존 배열 길이 만큼 이중 탐색을 진행하며, 부분합을 진행합니다.
3. 부분합의 결과는 HashSet에 추가합니다.
4. 결과적으로 HashSet의 크기를 정답 처리합니다.

📌 코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        
        HashSet<Integer> set = new HashSet<Integer>();
        ArrayList<Integer> lst = new ArrayList<Integer>();
        for (int i = 0; i<2; i++) {
            for (int element : elements) {
                lst.add(element);
            }
        }
        for (int i = 0; i < elements.length; i++) {
            for (int j = 1; j <= elements.length; j++) {
                List<Integer> subLst = lst.subList(i, i+j);
                int sum = 0;
                for (int num : subLst)
                    sum += num;
                set.add(sum);
            }
        }
        answer = set.size();
        return answer;
    }
}

✏️ TIP : subList를 활용하여 리스트를 슬라이싱할 수 있습니다.

위에서는 기존 배열에 배열을 이어 붙여 문제를 해결했지만, 아래 코드와 같이 기존 배열만으로도 문제를 해결할 수 있습니다.

-> elements[k%elements.length]와 같이 해당 나머지 연산으로 도출된 인덱스를 활용해 누적합을 도출할 수 있습니다.

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();
    }
}

피드백 및 개선점은 댓글을 통해 알려주세요😊