LV2 연속 부분 수열 합의 개수 (Java)

 

---

 

문제

 

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

프로그래머스

 

풀이

이 문제의 핵심은, 수열합을 구할때 이미 구한 부분을 어떻게 다시 계산하지 않고 구할 수 있느냐이다. 

(만약 수열때마다 모든 합을 구하면 1000 (원소의 개수) * 1000 (수열의 최대 길이) * 1000 (수열합 구하기) 의 시간 복잡도가 나오게 될 것이다..)

 

[1, 2, 3, 4] 배열이 있을때 수열 2인 값을 구할때 [1, 2] 의 합을 구하게 될 것이다.

그리고 수열3인 값을 구할때 [1, 2, 3]의 합을 구할텐데, 잘 생각해보면 [1, 2] 값은 이미 구한값이기 때문에 이를 어디 저장해두었다가 [3]만 더해주면 값을 구할 수 있다.

 

하나씩 예시로 들어보자면,

 

수열이 1인 값의 배열은 [1, 2, 3, 4] 가 된다.

 

수열이 2인 값의 배열은

[3, 5, 7, 5] 가 된다.

 

3은 어떻게 나왔을까?

기존 값인 1에서, 자신의 위치에서 1만큼 떨어진 값인 2를 더해서 나온 값이다.

 

5는 어떻게 나왔을까?

기존값인 2에서, 자신의 위치에서 1만큼 떨어진 값인 3을 더해서 나온 값이다.

 

이런식으로 최대 수열의 길이까지 반복하며 기존값과 새로운 위치값을 더해주면서 반복해주면 해결할 수 있다.

 

*위치값 같은 경우에는 배열의 최대 길이를 넘어갈 수 있기에 mod 연산을 해준다.

  (최대 길이가 5인데 4에서 2만큼 떨어진 경우에는 1이 될것이다.)

 

*중복은 set 자료구조를 활용하여 제거하였다.

 

코드

import java.util.*;

class Solution {
    
    public int solution(int[] elements) {
        Set<Integer> s = new HashSet<>();

        int len = elements.length;
        
        List<Integer> dp = new ArrayList<>();
        for(int i=0; i<len; i++){
            s.add(elements[i]);
            dp.add(elements[i]);
        }
        
        for(int i=1; i<len; i++){
            for(int j=0; j<len; j++){
                int targetIdx = (i+j)%len; // 범위를 넘어갈 수 있기에
                s.add(dp.get(j) + elements[targetIdx]);
                dp.set(j, dp.get(j) + elements[targetIdx]);
            }
        }
        return s.size();
    }
}

 

후기

 

처음에는 배열 두개를 사용해서 deepcopy를 사용하면서 풀었는데, 풀이를 보니 배열 하나로도 풀 수 있는걸 깨달았다.

 

dp생각은 안했는데, 풀어보고 나니 dp더라.