[Programmers / Level 2] 131701. 연속 부분 수열 합의 개수 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131701
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/연속 부분 수열 합의 개수

입출력 조건

입출력 예시

문제 이해

• 원형 배열에서 연속된 부분 수열들의 합을 구하고, 그 합이 몇 종류인지 세는 문제

알고리즘

풀이 시간 : 18분

• 원형 배열 -> 배열을 2배로 확장해서 연속 처리하듯이 배열
• 길이 1 ~ 배열 전체 길이까지의 모든 연속 부분 수열 합 구하기
• 중복 없이 set에 넣어서 개수 반환하기

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> set = new HashSet<>();
        int len = elements.length;
        int[] extended = new int[len * 2];
        for (int i = 0; i < len * 2; i++) {
            extended[i] = elements[i % len];
        }

        // 모든 길이의 연속 부분 수열 합 계산
        for (int size = 1; size <= len; size++) {
            for (int start = 0; start < len; start++) {
                int sum = 0;
                for (int i = start; i < start + size; i++) {
                    sum += extended[i];
                }
                set.add(sum);
            }
        }

        return set.size();
    }
}

결과