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

 

문제

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

 

 

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

---

입출력 예

 

 

---

입출력 예 설명

입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

 

 

---

 

분석

1. 연속한다고 해서 단순이 양옆 수의 합으로 생각했는데, 연속되는 수를 몇 개까지로 치는지를 별개로 생각해야 한다.
2. 1번 연속하면 2개의 수 합이 되고, 2번 연속하면 3개 수의 합이 된다. 합을 구할 연속 부분 수열의 길이는 최소 1부터 elements.length 까지.
3. 그리고 가장 중요한 건 도출할 수 있는 값들에서 중복을 제거하고 남은 수들의 총 개수를 구해야 한다.
4. 길이에 대한 for문이 있고, 시작 위치에 대한 for문으로 이중 for를 이용해 구할 수도 있을 것 같은데.
5. 그런데 이중for문을 이용할 경우 시간효율이 너무 떨어질 것이 우려되는데... 일단 구현해보자.
6. 최대 길이는 elements.length 인데, 결국 모든 요소를 다 더한 값은 시작점이 어디든 동일하기 때문에 이 합계값은 한 번만 구해주면 됨. 
7. 시작점 elements[i] 가 있고  -> 여기에 elements[i+1]인 값을 더하여 나온 값,  -> 여기에 elements[i+2]인 값을 더하여 나온 값... 이런 식으로 누적해가면 될 것 같다.

 

 

 

---

 

피드백

1. 풀긴 풀었으나... 테스트케이스에서 시간이 상당히 오래걸린 경우가 있어 반성. 주어진 배열 변수의 length 만큼의 for를 두 번이나 이중으로 돌리다보니까 시간이 오래걸릴거라고 생각은 했는데, 이걸 회피할 좋은 방법이 생각이 나지 않았다. 
2. 다른 사람의 풀이를 보니 동적 계획법(DP 알고리즘)으로 풀어낸 것 같은데, 사실 어떻게 완전 차이가 나는지 단번에 이해가 안 됐다. 알고리즘 지식의 차이인가... 분발하자... 알고리즘공부의 필요성을 더욱 느낀다. 

 

 

 

---

 

답안

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int len = elements.length;
        Set sumSet = new HashSet();	// 합계의 값을 가질 객체(중복 불가)
        
        int sumAll = 0;             // 전체 요소의 합계(모든 경우에 동일하므로 1회만 합산)
        for(int i = 0; i < len; i++) {			// 시작 위치의 for문
        	int sum = 0;
        	sumAll += elements[i];
        	
        	for(int j = 0; j < len-1; j++) {		// 길이의 for문
        		sum += elements[(i+j) % len];
        		sumSet.add(sum);
        	}
        }
        sumSet.add(sumAll);
        
        return sumSet.size();
    }
}

 

 

 

---

 

다른 사람의 답안

import java.util.*;

class Solution {
        public int solution(int[] elements) {
            Set<Integer> set = new HashSet<>();
            int[] dp = new int[elements.length];
            for(int len = 1;len <= elements.length; len++){
                for(int i = 0;i<elements.length;i++){
                    dp[i] += elements[(len+i-1)%elements.length];
                    set.add(dp[i]);
                }
            }
            return set.size();
        }
    }

 

🤖 챗지의 분석

(사실 나는 내 코드랑 달리 dp가 왜 들어가서 저렇게 쓰여야하는지 한번에 이해를 하지는 못 했는데, 챗지의 말을 더듬더듬 이해해가고 있다....)

 

핵심 차이점

1. 누적 방식 (각각의 시작 인덱스와 전체 배열 길이):
   • 코드 A에서는 sum 변수를 사용해 매번 i번째 시작 인덱스에 대해 새로운 부분합을 계산합니다. 즉, sum은 각각의 시작 인덱스마다 초기화되며, 그 인덱스에서 시작하는 모든 부분 배열의 합을 계산합니다.
   • 코드 B에서는 dp 배열을 사용하여 각 인덱스 i마다 누적된 값을 기록합니다. dp[i]는 i번째 인덱스까지의 누적합을 저장하며, 각 len에 대해 누적합을 계산합니다.
2. 구현 방식의 차이점:
   • 코드 A에서는 sum을 매번 초기화하고, 해당 인덱스에서 시작하는 부분 배열을 한 번에 계산합니다.
   • 코드 B에서는 dp[i]가 누적합을 저장하는 역할을 하고, len 길이에 따라 동적으로 값을 갱신합니다. 즉, dp 배열을 사용하면 각 인덱스에 대한 부분합을 계속 누적할 수 있습니다.
3. 효율성:
   • 코드 A는 매번 sum을 초기화하고 각 부분 배열을 별도로 계산하기 때문에, 부분합을 반복적으로 계산하는 방식입니다.
   • 코드 B는 dp[i] 배열을 사용하여 누적합을 계산하므로, 동적으로 누적된 값을 갱신하면서 중복된 계산을 피할 수 있습니다. 이로 인해 좀 더 효율적인 방식입니다.

예시 비교

• 코드 A 예시 (예: elements = [1, 2, 3]):
  • i = 0일 때: sum은 1 -> 3 -> 6 (부분합들)
  • i = 1일 때: sum은 2 -> 5 -> 8
  • i = 2일 때: sum은 3 -> 6 -> 9
• 코드 B 예시 (예: elements = [1, 2, 3]):
  • dp[0] = 1, dp[1] = 2, dp[2] = 3 (길이 1 부분합)
  • dp[0] = 3, dp[1] = 5, dp[2] = 4 (길이 2 부분합)
  • dp[0] = 6, dp[1] = 6, dp[2] = 6 (길이 3 부분합)

결론적으로, 코드 A에서의 sum은 각 i에서부터 연속적인 부분 배열 합을 하나씩 누적하는 방식이고, 코드 B에서는 dp 배열을 활용해 누적합을 동적으로 업데이트하며, 중복 계산을 피하고 효율적으로 합을 구하는 방식입니다.

 

💡 DP 알고리즘이란 ?

**동적 계획법(DP, Dynamic Programming)**은 문제를 더 작은 하위 문제들로 나누어 해결하고, 그 해결 결과를 저장하여 중복 계산을 피하는 알고리즘 기법입니다. 주로 최적화 문제를 해결하는 데 사용되며, 그 핵심 아이디어는 겹치는 하위 문제를 한 번만 계산하고, 그 값을 저장해 재사용하는 것입니다.

동적 계획법의 핵심 개념

1. 하위 문제로 분할: 큰 문제를 작은 하위 문제로 나누어 해결합니다.
2. 중복 계산 피하기: 같은 하위 문제가 여러 번 계산되는 것을 피하고, 한 번 계산된 결과를 저장하여 재사용합니다.
3. 최적 부분 구조: 큰 문제를 작은 문제로 나누었을 때, 작은 문제의 최적 해가 전체 문제의 최적 해를 구성한다는 특성이 있어야 합니다.
4. 메모이제이션/탑다운 또는 타뷸레이션/바텀업 방식으로 해결 결과를 저장합니다

동적 계획법의 특징

• 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 해결한 후 그 결과를 저장하여 나중에 재사용합니다.
• 시간 복잡도가 효율적입니다. 일반적으로 O(n) 혹은 **O(n²)**로 해결할 수 있습니다.
• 메모리를 사용하여 계산된 값을 저장하고, 중복 계산을 피하기 때문에 시간을 절약할 수 있습니다.

동적 계획법을 사용하는 문제들

• 피보나치 수열 (Fibonacci Sequence)
• 배낭 문제 (Knapsack Problem)
• 최단 경로 문제 (Shortest Path Problem) — 예: 다익스트라 알고리즘
• 최대 부분합 문제 (Maximum Subarray Problem)
• 문자열 편집 거리 (Edit Distance)

 

---

 

🔗링크

프로그래머스