[프로그래머스 코딩테스트] 연속 부분 수열 합의 개수(Java)

  문제 설명

  철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4]로 원형 수열을 만들면 다음과 같습니다.

이미지 출처: 프로그래머스, 연속 부분 수열 합의 개수

  원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

  원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

 

  제한사항

• 3 <= elements의 길이 <= 1,000
• 1 <= elements의 원소 <= 1,000

 

  입출력 예

elements	result
[7, 9, 1, 1, 4]	18

import java.util.HashSet;
class Solution {
    public int solution(int[] elements) {
        HashSet<Integer> set = new HashSet<>();
        int len = 1;
        while (len <= elements.length) {
            int sum = 0;
            for (int i = 0; i < len; i++) {
                sum += elements[i];
            }
            set.add(sum);
            for (int i = len; i < elements.length + len; i++) {
                int index = i % elements.length;
                sum = sum - elements[i - len] + elements[index];
                set.add(sum);
            }
            len++;
        }
        int answer = set.size();
        return answer;
    }
}

  중복되는 수를 방지하기 위해 HashSet을 생성합니다.

  부분 수열의 길이를 담을 변수 len을 생성합니다.

  while문이 len이 elements의 길이보다 작거나 같아질 때까지 반복문을 실행합니다.

  변수 sum을 생성합니다.

  슬라이딩 윈도우 알고리즘을 쓸 것입니다. 따라서 첫 번째 for문으로 슬라이딩 윈도우의 초기 값을 만듭니다. i가 len만큼 순회합니다. elements의 i번째 원소를 sum에 더하기 할당합니다.

  add 메소드를 이용하여 구한 값을 set에 추가합니다.

  두 번째 for문은 남은 원소의 합을 구할 것입니다. 앞서 각 길이당 초기 값을 구했으므로 이를 제외하고 len부터 시작하여 elements의 길이에 len을 더한 값만큼 순회합니다. 원형 수열이기 때문입니다.

  변수 index를 생성합니다. i를 elements의 길이로 나눈 값의 나머지를 할당합니다. for문이 순회하는 부분이 배열의 길이를 초과하므로 오류가 발생하지 않도록 방지하는 것입니다.

  sum에 sum에서 elements의 i - len 번째 원소를 뺀 뒤 elements의 index 번째 원소를 더합니다. 이는 투 포인터 알고리즘으로 생각해보면 포인터의 위치를 변경하는 것과 동일합니다. 포인터를 이동했으니 이동하기 전 부분의 값은 빼고, 이동한 부분의 값은 더해주는 것입니다.

  이렇게 구한 값을 add 메소드를 이용하여 set에 추가합니다.

  for문이 모두 끝나면 len이 증가하여 다음 길이만큼 슬라이딩 윈도우 알고리즘을 반복합니다. 이는 앞서 설명했듯 len이 elements의 길이에 다다를 때까지입니다.

  set 자료구조는 중복을 허용하지 않으므로 중복되는 원소는 자동으로 제거된 상태입니다. 따라서 set의 size를 반환하면 원형 수열의 연속 부분 수열의 합으로 만들 수 있는 개수를 모두 구할 수 있습니다.