[프로그래머스] 연속 부분 수열 합의 개수 / 자바(Java)

문제

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

프로그래머스

 

---

해설

원형배열이 나오는 문제입니다. 

이 경우 인덱스를 어떻게 관리하느냐가 중요한데 기존의 값을 넘긴 경우 0으로 되돌리는 방법은 부분합을 구해야하는 과정에서 계산이 복잡하게되어 기본배열을 뒤에 하나더 붙인 2배길이 배열을 만들어 해결하였습니다.

또한 부분합이 중복된 경우는 제외하고 구하므로 Set자료구조를 사용해 자동으로 중복을 제외시켜줍니다.

 

이후 범위가 1000인 비교적 작은 값이므로 3중 for문을 이용해 부분배열의 길이만큼 각 위치에서 시작할 수 있도록 값을 더해줍니다.

주의점

• 원형수열은 인덱스를 관리해주어야한다
  • 기본 배열의 2배 길이의 배열을 만들어 주기
  • 더한 후의 값을 기본 배열의 길이만큼 나눈 나머지를 인덱스로 사용하기

---

코드

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        int[] newElements = new int[elements.length*2];
        for(int i=0;i<elements.length;i++){
            newElements[i] = elements[i];
            newElements[i+elements.length] = elements[i];
        }
        
        Set<Integer> s = new HashSet<>();
        // i = 부분배열길이
        for(int i=1;i<=elements.length;i++){
            // j = 시작 인덱스
            for(int j=0;j<elements.length;j++){
                int cur_sum = 0;
                // k = 부분배열 인덱스
                for(int k=0;k<i;k++){
                    cur_sum += newElements[j+k];
                }
                s.add(cur_sum);
            }
        }
        return s.size();
    }
}