[오늘의 문제] 연속 부분 수열 합의 개수

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

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
그림.png
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
입출력 예
elements result
[7,9,1,1,4] 18
입출력 예 설명
입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

두번째 문제도 set을 활용하는 문제였다.
2레벨부터는 항상 어떤 자료구조를 활용해야 하는가 부터 고민해보기

class Solution {
public int solution(int[] elements) {
int answer = 0;
// 원형 수열의 모든 원소 elements
// 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return
int arr[] = new int[]
for(int i = 0; i < elements.length; i++){

        // 길이가 1일때
        // 2일때
        // 3일때
        //.. 4일때
        // 5(배열원소길이만큼)일때    
        
        answer++;
    }
    
    
    return answer;
}

}

..아예 접근조차도 못한 문제였다. 그렇다면 다른분들은 어떻게 풀었는지 보자.

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

class Solution {
public int solution(int[] elements) {
// elements의 2배 크기의 배열 생성
int[] newElements = new int[elements.length * 2];

    // newElements의 i와 i + elements.length 위치에 elements[i] 저장
    for(int i = 0; i < elements.length; i++) {
        newElements[i] = elements[i];
        newElements[i + elements.length] = elements[i];
    }

    // 중복을 제거하기 위한 Set 생성
    Set<Integer> set = new HashSet<>();

    // 부분 수열의 합 구하기
    for(int i = 0; i < elements.length; i++) {
        for(int j = 0; j < elements.length; j++) {
            // 새 배열에서 j부터 j+i-1까지의 부분 배열의 합을 구하고 Set에 추가
            set.add(Arrays.stream(newElements, j, j+i).sum());
        }
    }

    // 개수 반환
    return set.size();
}

}

newElements 배열은 원본 배열의 두 배 크기의 배열을 새로 만든다

그리고, 그밑의 반복문은 원형 수열처럼 만들기 위해 뒤에 원본을 한 번 더 붙인 것.

set특징은 중복이 안되고, 순서가 없다는 것.
중복이 안되게 set에 저장을 한다.

위의 set은 중복을 제거한 합들을 저장하는 집합이다.

Arrays.stream(array, from, to)는 from부터 to-1까지의 합을 구함

그외에 다른 풀이

import java.util.*;

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

    for(int i = 0; i < length; i++) {
        int temp = elements[i];
        set.add(temp);
        for(int j = i + 1; j < i + length; j++) {
            if(j >= length) {
                temp += elements[j - length];
                set.add(temp);
            } else {
                temp += elements[j];
            set.add(temp);
            }
        }
    }
    
    return set.size();
}

}

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

class Solution {
public int solution(int[] elements) {
Set sums = new HashSet<>(); // 합을 중복없이 저장할 Set

    int n = elements.length;

    for (int len = 1; len <= n; len++) { // 부분 수열 길이 1부터 n까지
        for (int start = 0; start < n; start++) { // 시작 인덱스 0부터 n-1까지
            int sum = 0;
            for (int i = 0; i < len; i++) { // 길이만큼 더하기
                sum += elements[(start + i) % n]; // 원형이니까 %n
            }
            sums.add(sum);
        }
    }

    return sums.size();
}

}