연속 부분 수열 합의 개수

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

프로그래머스

 

연속 수열의 부분합을 구했을 때, 중복되지 않은 부분합의 개수를 구하는 문제다.

 

처음엔 elements 배열을 재배열해가며 계산 했는데...

 

생각해보니 index 값만 잘 조절하면 재배열하는 행위가 필요 없음을 깨달았따.

 

for문이 3번이나 돌아야 해서 타임아웃을 걱정했는데 별 문제 없이 통과함..

 

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        
        Set<Integer> res = new HashSet();
        int len = elements.length;
        // 부분 수열 원소 개수
        for (int i = 1; i <= len; i++) {
            // 시작 원소 위치
            for (int j = 0; j < len; j++) {
                int sum = 0;
                // 시작 원소 부터 k 위치까지(j + i)의 부분합
                for (int k = j; k < j+i; k++) {
                    sum+=elements[k%len];   // 마지막 원소 이후에는 첫 원소부터 시작해야하므로 k를 len의 나머지값을 index로 설정
                }
                res.add(sum);
            }
            
        }
        
        return res.size();
        
    }
}