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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 연속 부분 수열 합의 개수

 

문제 접근

처음에는 백트래킹을 사용해서 문제를 풀었다.

 

먼저 처음 매개변수로 넘어온 elements를 똑같이 연결해서 마치 원형 수열처럼 만들었다.

ex) 1,2,3 수열 --> 1,2,3,1,2,3 

 

이렇게 만들고 나서 백트래킹을 사용 

 

return 조건

1. 현재 커서(depth) 더 이상 사용할 원소가 없는 경우

2. 연속 부분 수열의 길이(size)가 처음 elements의 총 크기와 같을 경우 

 

백트래킹 내부 로직

1. 이번 커서의 원소를 시작으로 두기

2. 이전 합을 기반으로 계속 수열을 이어 나가기 

 public static void function(int depth, int sum, int size){
    if(size == max || depth == max * 2 - 1){
        return;
    }
    // 새로운 시작    
    set.add(circularElements[depth]);
    function(depth + 1, circularElements[depth], 1);

    // 이어서 계속 
    set.add(circularElements[depth] + sum);
    function(depth + 1, circularElements[depth] + sum, size + 1);

}

 

정답은 잘 나왔지만 역시 시간 초과가 발생한다. 

2^n(수열의 크기)으로 함수 호출(function)이 일어난다.

 

elements 크기가 1000이면 시간 복잡도는 대략 O(2^1000)

시간 초과 코드

import java.util.*;
class Solution {
    static int[] circularElements;
    static Set<Integer> set = new HashSet<>();
    static int max;
    public int solution(int[] elements) {
        max = elements.length;
        circularElements = new int[max * 2];
        for(int i = 0; i < max; i++){
            circularElements[i] = elements[i];
        }
        for(int i = max; i < max * 2; i++){
            circularElements[i] = elements[i - max];
        }
        function(0, 0, 0);    
        return set.size();
    }
    public static void function(int depth, int sum, int size){
        if(size == max || depth == max * 2 - 1){
            return;
        }
        // 새로운 시작    
        set.add(circularElements[depth]);
        function(depth + 1, circularElements[depth], 1);
        
        // 이어서 계속 
        set.add(circularElements[depth] + sum);
        function(depth + 1, circularElements[depth] + sum, size + 1);
        
    }
}

 

 

이번에는 누적합을 사용했다. 

연속 부분 수열의 합은 누적합을 먼저 구하고 2중 for문을 통해서 구하는게 가능하다. 

ex) 크기가 1인 연속 부분 수열:  prefix[idx+1] - prefix[idx] 

 

원형 수열 만드는 로직 

for(int i = 0; i < max; i++){
    circularElements[i] = elements[i];
}
for(int i = max; i < max * 2; i++){
    circularElements[i] = elements[i - max];
}

 

누적합 로직

int [] prefixSum = new int [max * 2 + 1];
for(int i = 1; i <= max * 2; i++){
    prefixSum[i] = prefixSum[i-1] + circularElements[i-1];
}

 

2중 for문을 통해 각 연속된 구간 구하기

중요!  각 구간의 크기는 elements 크기를 넘으면 안 된다. 

for(int i = 0; i <= max * 2; i++){
    for(int j = i+1; j <= max *2; j++){
        if(j - i > max) break;
        set.add(prefixSum[j] - prefixSum[i]);
    }    
}

 

set의 크기를 return 하면 끝!

정답 코드

import java.util.*;
class Solution {
    static int[] circularElements;
    static Set<Integer> set = new HashSet<>();
    static int max;
    public int solution(int[] elements) {
        max = elements.length;
        circularElements = new int[max * 2];
        for(int i = 0; i < max; i++){
            circularElements[i] = elements[i];
        }
        for(int i = max; i < max * 2; i++){
            circularElements[i] = elements[i - max];
        }
        
        int [] prefixSum = new int [max * 2 + 1];
        for(int i = 1; i <= max * 2; i++){
            prefixSum[i] = prefixSum[i-1] + circularElements[i-1];
        }
        for(int i = 0; i <= max * 2; i++){
            for(int j = i+1; j <= max *2; j++){
                if(j - i > max) break;
                set.add(prefixSum[j] - prefixSum[i]);
            }    
        }
        return set.size();
    }
}