문제 출처
문제
철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
나의 풀이(통과)
처음엔 어렵게 생각해서 for문을 len만큼 도는 게 아니라 무한하게 많이 돌아야 한다고 생각했다.
그러나 잘 생각해보면,
원형으로 이어져 있어도 결국 시작지점은 len 내부에 있을 수 밖에 없고, 증가폭만이 cnt+1만큼 늘어난다.
그 증가폭은 기껏해서 len*2일수밖에 없다.
예를 들어 아래 tc 배열에서 마지막 요소인 4에서 5개를 더한다고 하면 4,7,9,1,1 을 더하는 건데 이래봤자 결국 [7,9,1,1,4,7,9,1,1,4]의 배열만 갖춰져 있으면 감당 가능하다.
그러므로 처음부터 배열을 elements를 쓰는 게 아니라 elements 2개를 이어붙인 arr에 대해서 slice 메서드를 사용하면 된다.
증가폭을 변수 cnt로 관리해서 cnt가 1,2,3,4,5인 동안 for문을 돌아서 값을 ans에 넣고 new Set으로 중복을 제거해준다.
무조건 재귀를 돌아서 완전탐색을 하려하지 말고,
이렇게 규칙을 찾으려고 노력하기.
- 규칙을 어떻게 찾냐면? => 몇 가지의 예시에서 힌트를 얻기.
-->> 이 문제에서는 마지막 요소에서 최대 길이만큼 slice하려면 어떤 조건이어야 하는지를 탐색해야 했다.
-->> 마지막 요소 4에서 길이 5만큼 탐색하려면,
단순하게 길이 5만큼만 배열을 더 만들어서 for문을 돌면 되는 구나. 라고 생각을 확장해 나가는 것.
function solution(elements) {
let ans = [];
let arr = elements.concat(elements);
let len = elements.length;
let cnt = 0;
while(cnt<len) {
for (let i=0; i<len; i++) {
let sum = arr.slice((i%len), (i%len)+(cnt+1)).reduce((a,b) => a+b);
ans.push(sum);
}
cnt++;
}
return [...new Set(ans)].length;
}
console.log(solution([7, 9, 1, 1, 4]));다른 풀이
Dynamic Programming
function solution(elements) {
const len = elements.length;
elements = [...elements , ...elements.splice(0, elements.length -1)];
const dp = new Array(elements.length + 1).fill(0);
dp[0] = 0;
for(let i = 0; i < elements.length; i++){
dp[i + 1] += dp[i] + elements[i];
}
const set = new Set();
set.add(dp[len]);
for(let j = 1; j < len; j++){
for(let i = 1; i < dp.length; i++){
if(i + j >= dp.length) continue;
set.add(dp[j + i] - dp[i]);
}
}
return set.size;
}