자바 - 프로그래머스 / 연속 부분 수열 합의 개수

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

프로그래머스

LV 2

 

구현 방법

3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000

삼중 포문까지 가능하고, 자료형은 int 써도 된다.  원형 수열을 구현 하는 방법은 "% 배열의 길이"를 이용하면 된다. 

1. 삼중 포문 사용

첫번째 포문 -  더할 원소 개수

두번째 포문 -  더할 원소의 시작 인덱스

세번째 포문 -  연속된 합을 구현하기 위해

 

하지만 현재 문제로는 런타임 에러가 나지 않지만, elements의 길이가 길어질 경우 런타임 에러가 발생할 가능성이 있다.

실제로 코드 돌려봐도 속도가 느리다. 따라서 삼중 포문을 이중 포문으로 바꿔서 다시 구현했다. O(n^3)을 O(n^2)로 바꾸기 위해 메모리를 많이 사용하는 방법인 dp를 이용할 것이다.(메모리, 시간 반비례 관계)

 

2. dp 이용

dp[원소 길이][원소 길이]를 만들어서 삼중 포문 사용 했을때 세번째 포문 역할을 대신 할 수 있다. 

다시 말해 n개의 연속된 합을 구함에 있어서 반복문 - O(n)을 사용하지 않고, n-1개의 연속된 합을 미리 저장하여 n번째의 원소만 더해주는 방식 - O(1)이다.

코드

1. 삼중 포문 사용

import java.util.Set;
import java.util.HashSet;

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

        for(int i = 1; i < elements.length + 1; i++) {
            for(int j = 0; j < elements.length; j++) {
                int sum = 0;
                for(int k = 0; k < i; k++) {
                    sum  += elements[(j + k) % elements.length];
                }
                set.add(sum);
            }
        }
        
        return set.size();
    }
}

 

1. dp 이용

import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

class Solution {
    public int solution(int[] elements) {
        
        Set<Integer> set = new HashSet<>();
        int[][] dp = new int[elements.length][elements.length];

        for(int i = 0; i < elements.length; i++) {
            Arrays.fill(dp[i], 0);
            dp[0][i] = elements[i];
            set.add(dp[0][i]);
        }

        for(int i = 1; i < elements.length; i++) {
            for(int j = 0; j < elements.length; j++) {
                dp[i][j] +=  dp[i - 1][j] + elements[(j + i) % elements.length];
                set.add(dp[i][j]);
            }
        }
        
        return set.size();
    }
}

1번, 2번 속도 차이가 크게 나는것을 볼 수 있다.

 

느낀 점

시간 복잡도를 줄이고 싶다면 메모리를 많이 사용하면 된다.

구간 합 유형의 알고리즘

 

비슷한 문제

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4