알고리즘 #0008

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따르면, 부분 수열의 총합의 개수를 구해야 한다.

---

• 수열의 최대 길이는 1000이므로 시간 복잡도는 최대 O(n$^3$)까지 고려해볼 수 있을 것이다.
• 배열을 원형 큐처럼 생각하고 순회하면서 배열의 사이즈가 될 때까지 크기를 늘려가며 순열의 합을 구한다
• 아래의 [코드 1]처럼 코드를 작성한다.

---

• [코드 1] 처음 작성한 코드 답안

import java.util.*;
class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= elements.length; i++) {
            for (int j = 0; j < elements.length; j++) {
                int sum = 0;
                for (int z = 0; z < i; z++) {
                    sum += elements[(j+z)%elements.length];
                }
                set.add(sum);
            }
        }
        return set.size();
    }
}

2. 실행 결과

• 모든 테스트 케이스에서 정상적으로 실행되었다.
• [결과 1]