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

코드 힌트

1. 중복을 제거하기 위해 HashSet 사용하기:
   • HashSet은 중복된 값을 자동으로 제거해줍니다. 이를 활용해 조합의 합을 저장합니다.
2. 연속된 부분 수열을 구하는 문제:
   • 주어진 배열에서 연속된 숫자들의 합을 구하는 문제입니다. 바로 옆에 이어지는 숫자들로 조합의 합을 계산해야 합니다.
3. 모든 길이의 연속된 부분 수열을 고려:
   • 조합의 길이는 1부터 배열의 길이까지 모두 포함됩니다. 즉, 모든 가능한 연속된 부분 수열을 구해야 합니다.
4. % 연산자를 사용하여 배열의 쉬프트 구현:
   • 원형 배열을 구현하기 위해 % 연산자를 사용합니다. 이를 통해 배열의 끝에서 다시 처음으로 돌아가는 순환 구조를 쉽게 처리할 수 있습니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    // 조합의 합을 저장할 HashSet
    HashSet<Integer> set = new HashSet<>();
    
    public int solution(int[] elements) {
        // 배열의 길이
        int n = elements.length;
        
        // 1부터 배열 길이까지의 조합 크기를 설정
        for (int r = 1; r <= n; r++) {
            // 원형 조합 생성 함수 호출
            circleCombination(elements, 0, n, r);
        }
        
        // 중복되지 않는 조합의 합의 개수를 반환
        return set.size();
    }
    
    // 원형 조합 생성 함수
    // start : 현재 위치, n : 배열 길이, r : 조합 크기
    public void circleCombination(int[] elements, int start, int n, int r) {
        if (start == n) {
            return;
        }
        // 조합의 합을 계산하여 집합에 추가
        sumCombination(elements, start, n, r);
        // 다음 위치로 이동하여 재귀 호출
        circleCombination(elements, start+1, n, r);
    }
    
    // 해당 조합의 합을 계산하여 집합에 추가하는 함수
    public void sumCombination(int[] elements, int start, int n, int r) {
        int result = 0;
        // start부터 start+r까지의 원형 조합을 계산
        for (int i = start; i < start + r; i++) {
            result += elements[i % n]; // 원형 배열의 특성을 고려하여 인덱스 계산
        }
        set.add(result); // 조합의 합을 집합에 추가
    }
}

 

주석 제거 코드

import java.util.*;

class Solution {
    HashSet<Integer> set = new HashSet<>();
    
    public int solution(int[] elements) {
        int n = elements.length;
        
        for (int r = 1; r <= n; r++) {
            circleCombination(elements, 0, n, r);
        }
        
        return set.size();
    }
    
    public void circleCombination(int[] elements, int start, int n, int r) {
        if (start == n) {
            return;
        }
        sumCombination(elements, start, n, r);
        circleCombination(elements, start+1, n, r);
    }
    
    public void sumCombination(int[] elements, int start, int n, int r) {
        int result = 0;
        for (int i = start; i < start + r; i++) {
            result += elements[i % n];
        }
        set.add(result);
    }
}