주어진 원순열에서 부분수열의 합을 구합니다. 이 때 나올 수 있는 합의 개수를 구하는 문제입니다. 중복없이 개수를 구해야 하기 때문에 모든 합들을 set
에 넣자는 아이디어를 떠올렸습니다. 또한 연속한 수열의 합이기 때문에 누적합을 이용하면 반복적인 계산을 생략할 수 있습니다.
prefixes
의 각 i
번째 row에 elements[i]
로 시작하는 수열의 누적합들을 기록합니다.
prefixes[i][j]
은 i
항부터 시작하는 길이가 j
인 부분수열의 합이 됩니다.
import java.util.*;
class Solution {
public int solution(int[] elements) {
int len = elements.length;
int[][] prefixes = new int[len][len + 1];
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < len; i++) {
int prev = 0;
for (int j = 0; j < len; j++) {
prefixes[i][j + 1] = prev + elements[(i + j) % len];
prev = prefixes[i][j + 1];
}
}
for (int i = 0; i < len; i++) {
for (int j = 1; j <= len; j++) {
set.add(prefixes[i][j]); // 굳이?
}
}
return set.size();
}
}
그런데 두번째 반복문을 잘 보면 작업이 set.add(prefixes[i][j])
뿐인데, 굳이 prefixes
라는 array
를 만들지 않더라도 바로 set
에 넣을 수 있습니다.
import java.util.*;
class Solution {
public int solution(int[] elements) {
int len = elements.length;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < len; i++) {
int prev = 0;
for (int j = 0; j < len; j++) {
prev = prev + elements[(i + j) % len];
set.add(prev + elements[(i + j) % len]);
}
}
return set.size();
}
}