
[프로그래머스] 연속 부분 수열 합의 개수(Java)
·
알고리즘
문제길이가 N인 원형 수열이 주어졌을 때, 길이 1부터 N까지 가능한 연속 부분 수열의 합을 모두 구하고, 그 중 서로 다른 값의 개수를 구하는 문제.🛠 사용 기술배열 슬라이딩 기법누적합(Prefix Sum)HashSet을 통한 중복 제거Approach 1 ⭕🔍 접근법모든 구간 길이(1 ~ N)에 대해 순회하며 (i + j) % N를 이용해 원형 수열을 처리하고, 모든 합을 HashSet에 저장해 중복을 제거했다.간단하지만 3중 루프 → 시간 복잡도: O(N³)입력 크기가 작기 때문에 통과되었지만, 대형 데이터에는 부적합💻 코드import java.util.*;class Solution { public int solution(int[] elements) { Set set = new..