[programmers] 연속 부분 수열 합의 개수 - Java
원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 찾는 문제에서는 주어진 배열을 두배로 늘려 원형 수열을 구현하고, 중복된 합을 방지하기 위해 HashSet을 사용한다. 세 개의 중첩 for문을 사용하여 모든 가능한 연속 부분 수열의 합을 계산한다. 하지만 이 방법은 퍼포먼스가 떨어진다는 단점이 있다.
Mar 07, 2024
연속 부분 수열 합의 개수
문제 설명
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소
elements
가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.제한사항
- 3 ≤
elements
의 길이 ≤ 1,000
- 1 ≤
elements
의 원소 ≤ 1,000
입출력 예
elements | result |
[7,9,1,1,4] | 18 |
입출력 예 설명
입출력 예 #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]
solution.java
import java.util.*; class Solution { public int solution(int[] elements) { int n = elements.length; int[] doubleElements = new int[2 * n]; for (int i = 0; i < n; i++) { // 기존 배열을 두배로 확장해서 원형 수열 구현 doubleElements[i] = elements[i]; doubleElements[i + n] = elements[i]; } HashSet<Integer> set = new HashSet<>(); // 중첩 방지를 위한 HashSet 사용 for (int i = 0; i < n; i++) { for (int j = i; j < i + n; j++) { // 시작 인덱스 int sum = 0; for (int k = i; k <= j; k++) { // 시작 인덱스부터 끝 인덱스까지의 부분 수열 합 계산 sum += doubleElements[k]; System.out.println(i+" " + j + " " +k); } set.add(sum); System.out.println(sum); } } return set.size(); } }
핵심 키워드
- 주어진 배열을 원형 수열로 처리하기 위해 배열을 두배로 늘려 끝과 처음을 연결한다.
- 중복된 합을 방지하기 위해 HashSet을 사용한다.
- 중첩 for문을 사용하여 모든 가능한 연속 부분 수열의 합을 계산한다.
- 첫 번째 반복문은 원본 배열의 시작 위치, 두 번째 반복문은 반복 시작 인덱스, 세 번째 반복문은 반복 종료 인덱스까지의 부분 수열의 합을 계산한다.
결론!
삼중 for문을 이용해서 문제를 풀었지만 퍼포먼스가 떨어지는 것을 느낄 수 있었다. 이를 해결하기 위해 코드를 찾아봐야겠다고 생각했다.
Share article