[프로그래머스 Lv2] 연속 부분 수열 합의 개수

연속 부분 수열 합의 개수

문제

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.
원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

---

풀이 로직

1. 원형 수열을 생성한다. ([7, 9, 1, 1, 4] ⇒ [7, 9, 1, 1, 4, 7, 9, 1, 1])
2. 첫번째부터 마지막 원소까지 순환하면서, 해당 원소부터 i개의 원소의 합을 구한다.
3. sums 배열에 해당 값이 없으면 추가한다.
4. sums 배열의 길이를 반환한다

---

코드

1. 시간 초과

function solution(elements) {
  const MAX_LENGTH = elements.length
  const array = [...elements, ...elements.slice(0, MAX_LENGTH - 1)];

  const sums = [];
  for (let i=1; i<=MAX_LENGTH; i++) {
    for (let j=0; j<MAX_LENGTH; j++) {
      const newArray = array.slice(j, j+i);
      const sum = newArray.reduce((sum, cur) => sum + cur, 0);
      if (!sums.includes(sum)) {
        sums.push(sum);
      }
    }
  }

  return sums.length;
}

elements의 길이가 1000까지 길어지면, 반복문 내 배열 메소드 slice와 reduce의 사용에 성능상 문제가 있을 것이라고 생각함.

---

2. 시간 초과

function solution(elements) {
  const MAX_LENGTH = elements.length
  const array = [...elements, ...elements.slice(0, MAX_LENGTH - 1)];

  const sums = [];
  for (let i=0; i<MAX_LENGTH; i++) {
    for (let j=0; j<MAX_LENGTH; j++) {
      let sum = 0;
      for (let k=j; k<=j+i; k++) {
        sum += array[k];
      }
      if (!sums.includes(sum)) {
        sums.push(sum)
      }
    }
  }

  return sums.length;
}

테스트 1 〉	통과 (0.07ms, 33.6MB)
테스트 2 〉	통과 (895.09ms, 37.6MB)
테스트 3 〉	통과 (3635.63ms, 38MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

slice와 reduce 대신 for문을 사용했는데도 시간초과가 나오는 것으로 보아 반복문 내 push 메소드 사용에 성능상 문제가 있을 것이라고 생각함.

---

3. Set 자료형 사용 ⇒ 해결

function solution(elements) {
  const MAX_LENGTH = elements.length
  const array = [...elements, ...elements.slice(0, MAX_LENGTH - 1)];

  const sums = new Set();
  for (let i=1; i<=MAX_LENGTH; i++) {
    for (let j=0; j<MAX_LENGTH; j++) {
      const newArray = array.slice(j, j+i);
      const sum = newArray.reduce((sum, cur) => sum + cur, 0);
      sums.add(sum);
    }
  }

  return sums.size;
}

---

Array vs Set

데이터가 많아질수록 (대략 100,000 이상) Set 자료형이 Array보다 더 나은 성능을 나타낸다.

Javascript Set vs. Array performance
[JS] Array vs. Set

---

💡 결론

시간초과의 압박이 있다면 Array 대신 Set을 사용하도록 하자.