[131701] 연속 부분 수열 합의 개수

✔ 연속 부분 수열 합의 개수

[프로그래머스 131701]

문제 분석하기

길이가 1일 때부터 elements의 길이까지의 부분 수열의 합의 구해 집합에 저장한 후, 집합의 갯수를 반환

손으로 풀어보기

1. 길이가 1일 때부터 elements의 길이까지의 부분 수열의 합의 구해 집합에 저장
   • 이때 처음과 끝이 연결되어 있는 원형 수열이므로 elements[j % elements의 길이]로 계산
2. 집합의 갯수를 반환

슈도코드 작성하기

elements(원형 수열의 모든 원소)
set(원형 수열의 연속 부분 수열 합을 저장하는 집합)
for(size -> 1부터 elements의 길이까지) {
    for(i -> 0부터 elemnts의 길이만큼) {
        sum(연속 부분 수열 합)
        for(j -> i부터 i + size만큼) {
            sum += elements[j % elements의 길이]
        }
        set에 sum 저장
    }
}
set의 크기 반환

코드 구현하기

/**
 * 131701) 연속_부분_수열_합의_개수
 */
public class L080_131701 {
    // elements(원형 수열의 모든 원소)
    public int solution(int[] elements) {
        // set(원형 수열의 연속 부분 수열 합을 저장하는 집합)
        Set<Integer> set = new HashSet<>();
        for (int size = 1; size <= elements.length; size++) {
            // 1부터 elements의 길이까지의 부분 수열의 합을 구함
            for (int i = 0; i < elements.length; i++) {
                // sum(연속 부분 수열 합)
                int sum = 0;
                for (int j = i; j < i + size; j++) {
                    // sum에 elements[j % elements의 길이] 추가
                    sum += elements[j % elements.length];
                }
                // set에 sum 저장
                set.add(sum);
            }
        }
        // set의 크기 반환
        return set.size();
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L080_131701 solution = new L080_131701();

        int[] elements = { 7, 9, 1, 1, 4 };

        int result = solution.solution(elements);

        System.out.println(result);
    }
}