[프로그래머스 / Java] Lv.2 연속 부분 수열 합의 개수

Question

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

프로그래머스

---

Algorithm

1. 중복 제거를 위해 HashSet을 사용한다.
   • 동일한 부분 수열 합이 여러 번 등장할 수 있기 때문에, 중복을 제거하고 서로 다른 합만 저장하기 위한 HashSet<Integer>를 사용
2. 주어진 배열 elements 길이 만큼 반복하며 부분 수열 길이를 결정한다.
   • for문을 사용해, 부분 수열의 길이를 size 변수로 선언하여 1부터 elements.length까지 모든 길이에 대해 순회
   • 가능한 모든 연속 부분 수열을 고려하기 위함
3. 초기 구간 합 계산 (부분 수열 시작점이 0일 때)
   • 각 길이별로 처음 나오는 부분 수열(ex. 인덱스 0부터 시작하는 길이 size짜리 수열)의 합을 먼저 계산하여 Set에 추가
4. 원형 수열을 고려한 슬라이딩 윈도우 기법
   • 시작 위치를 1씩 이동하며 이전 합에서 맨 앞 값을 빼고, 새로 포함된 값을 더해 다음 부분 수열의 합을 효율적으로 계산
   • 원형 수열이므로 인덱스 범위를 벗어날 경우 mod 연산을 사용해 다시 처음으로 돌아감
5. 계산된 각 부분 수열 합을 Set에 추가
   • Set을 사용함으로써 자동으로 중복이 제거되고, 유일한 합만 저장됨
6. Set의 크기를 반환
   • 결국 Set에 저장된 서로 다른 부분 수열 합의 개수가 정답이므로, Set.size()를 반환

---

Code

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        
        // 중복 없는 합을 저장할 Set
        Set<Integer> sumSet = new HashSet<>();
        
        int length = elements.length;
        
        // size : 부분 수열의 길이 (1부터 length까지)
        for(int size = 1; size <= length; size++) {
            int sum = 0;
            int start = 0;
            
            // 초기 부분 수열 합 계산 (맨 앞에서 size 길이 만큼)
            for(int i = 0; i < size; i++) {
                sum += elements[i];
            }
            // 합을 Set에 추가
            sumSet.add(sum);
            
            // start를 1씩 증가시키며 다음 부분 수열 합 계산 (원형 수열 처리)
            while(start < length - 1) {
                // 부분 수열의 맨 앞 값을 제거하고
                sum -= elements[start];
                // 다음 위치 값을 더함 (원형이므로 % length 처리)
                sum += elements[(start + size) % length];
                start++;
                
                // 새로 계산된 합을 Set에 추가
                sumSet.add(sum);
            }
        }
        
        // 서로 다른 합의 개수가 정답
        answer = sumSet.size();
        return answer;
    }
}

---

출처

https://dev-ddol-e.tistory.com/34

[ 프로그래머스 JAVA ] 연속 부분 수열 합의 개수