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

< 풀이 >

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        Set<Integer>set=new HashSet<>();
        
        int count=1;
        while(count<=elements.length){ // 길이 1 ~ 배열의 길이만큼 연속 부분 수열 구하기 
            for(int i=0;i<elements.length;i++){
                int sum=0;
                
                for(int j=i;j<i+count;j++){
                    sum+=elements[j%elements.length]; // 원형 배열이므로 인덱스를 j % elements.length 로 설정 
                }
                set.add(sum);
            }
            count++;
        }
        
        return set.size();
    }
}

 

✏️ 풀이 방법

 

1. 길이가 1부터 배열의 길이까지 연속 부분 수열을 구하기 위해 반복문 ① 을 돈다. 

   - 반복문 ② ( 인덱스 0 부터 배열의 길이까지 )

     

         - 반복문 ③ ( 인덱스 i부터 시작해서 i + count 까지 반복문, 즉 인덱스 i부터 시작해서 count 개 (연속 부분 수열의 길이가 count)

                          만큼의 합을 구하는 것이다. ) 

          : 원형 배열이므로 배열 인덱스가 배열의 크기를 초과했을 때를 고려해야한다. 그러므로 인덱스를 j % elements. length 로

            설정한다.

            ex) 배열의 길이가 5일 때, 현재 j의 값이 5라면 sum에 elements[0] 의 값을 더해준다. 

 

   : 반복문 ③ 에서 구한 sum 값을 중복을 허용하지 않는 HashSet에 넣어준다.

 

2. HashSet은 중복을 허용하지 않으므로, HashSet의 크기가 곧 연속 부분 수열 합의 개수이다. 

 

✍🏻 느낀점

 

 저번에도 느꼈던 거지만, 나는 정말 3중 반복문에 약한 것 같다. 이번 문제를 손 풀이로는 알겠는데, 반복문으로 구현하려고 하니까 너무 헷갈려서 다른 사람들의 풀이를 보고 나서야 이해를 했다. 막상 보면 별 거 아닌데, 왜 떠오르지가 않는거지..!! 이번 문제를 통해 다시 한 번 깨달았으니 너무 어렵게 생각하지 말아야지. 또 이번 문제를 통해 HashSet 이라는 것도 처음 알게 됐다. 배웠으니 다음에 중복을 허용하지 않는 문제가 나오면 잘 써먹어 봐야겠다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 

---

https://velog.io/@acacia__u/hashSet