https://school.programmers.co.kr/learn/courses/30/lessons/131701
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements
가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
elements | result |
---|---|
[7,9,1,1,4] | 18 |
길이가 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]
import java.util.HashSet;
class Solution {
public int solution(int[] elements) {
int answer = 0;
HashSet<Integer> set=new HashSet<>();
int len=elements.length;
for(int i=0;i<len;i++){
set.add(elements[i]);
}
int start=2;
while(start<=len){
for(int i=0;i<len;i++){
int sum=0;
int index=i;
for(int j=0;j<start;j++){
sum+=elements[index];
index++;
if(index==len) index=0;
}
set.add(sum);
}
start++;
}
answer=set.size();
return answer;
}
}
해시셋
을 이용했다. 알아서 중복된 값을 제거해주니까.
먼저 len
길이만큼 반복문을 돌려준다.
그리고 또 len
길이만큼 반복을 돌려주는데 만약 len이 5이면 2, 3, 4, 5 씩으로 늘려서 연속된 수열을 저장할 것이다. 즉, start만큼 길이를 지정해 연속 부분 수열의 합을 구한다.
만약, index
값이 len
길이와 같아지면, ex)7,9,1,1,4 에서 4와 연속된 7의 합을 구하는 경우
index
값을 0
으로 바꿔주어 연속된 수열의 합을 구하도록 했다.