[JAVA/프로그래머스] 연속 부분 수열 합의 개수 문제 풀이

안녕하세요.

프로그래머스 기준 Lv.2 정답률 67% 문제를 풀어 보도록 하겠습니다.

 

주어진 문제는 배열 'elements' 가 있을 때, 모든 가능한 연속적인 부분 배열의 합을 구하고, 이러한 합들 중 중복된 값을 제외하고 유니크한 값의 개수를 반환하는 것입니다. 배열이 수환적이라는 것이 핵심 포인트로, 배열의 끝에 도달하면 다시 시작 지점으로 돌아갑니다.

 

이 문제를 해결하기위해, 두 개의 중첩된 루프를 사용하여 모든 가능한 부분 배열의 합을 계산하고  'HashSet' 을 사용하여 중복을 제거했습니다.'HashSet' 은 고유한 요소만 저장하므로 , 따로 메소드를 만들지 않고 걸러낼 수 있습니다.

 

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

        for(int i=0; i< maxLength; i++){
            int sum=0;
            for(int j=0; j< maxLength; j++){
                sum += elements[(i+j) % maxLength];
                que.add(sum);
            }
        }

        return que.size();
    }
}

이 코드는 먼저 최대 길이를 배열의 길이로 설정합니다. 바깥쪽 루프는 배열의 각 시작 지점을 반복하고, 안쪽 루프는 해당 시작 지점부터 순환적으로 합을 계산합니다. '%' 연산자는 순환을 처리하게 되며 계산된 합은 'HashSet' 에 추가되어 고유값만 유지 됩니다.

 

• 시간 복잡도 : 해당 알고리즘은 O(n²) 입니다. 두 개의 중첩된 루프 때문입니다.
• 공간 복잡도 : 추가적인 공간은 주로 'HashSet'에 의해 사용되며, 이는 최대  O(n²)의 공간을 사용할 수 있습니다.

이 문제를 통해 순환 배열과 해시셋을 사용하여 문제를 풀 수 있습니다.