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

[프로그래머스 / JavaScript] 연속 부분 수열 합의 개수 - Level.2

문제: 연속 부분 수열 합의 개수 - Level.2

---

문제 설명

철호는 어떤 자연수로 이루어진 원형 수열의
연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보려한다.

• 원형 수열: 일반적인 수열에서 처음과 끝이 연결된 형태의 수열

예를 들어 수열 [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]

---

풀이 설명

해당 문제를 풀기 위해 다음과 같이 접근 법을 나눠봤다.

1. 해당 수열에서 연속 부분 수열 구하기
2. 수열이 원형 수열인 점을 고려하여 작성하기
3. 각 부분 수열의 합을 중복 없이 모아두기

먼저 수열에서 연속 부분 수열을 구하기 위해, 투 포인터 기법을 생각했다.

• 다음과 같이, 두 개의 포인터를 바꿔가며 구간을 정하여 값을 계산한다.
  
• 해당 방식으로 연속 부분 수열을의 합을 나열하여 구할 수 있다.

  function solution(elements) {
    const hap = [];
    for (let i = 0; i < elements.length; i++) {
        let sum = 0;
        let tmp = [];
        for (let j = 0; j < elements.length - i; j++) {
            sum += elements[i + j];
            tmp.push(sum);
        }
        hap.push(tmp)
    }
    console.log(hap);
    return
  }
  

  

그러나, 해당 수열이 원형 수열인 점을 주목하여, 다음과 같이 원형인 수열에서 푸는 방식을 변경해본다.
길이가 4인 연속 부분 수열에서를 가정하면.

• 일반 수열에서는 다음과 같이, 2가지 경우만이 존재한다.
  
• 원형 수열에서는 순환성을 고려하여 같은 배열을 2개를 연결해서 계산하도록 한다.
  
• 따라서, 다음과 같이, 수열 2개를 연결해서 원형 수열로 만들고 계산한다.

  function solution(elements) {
    const circlePer = [...elements, ...elements] // 수열 2개 연결
    const hap = [];
    for (let i = 0; i < elements.length; i++) {
        let sum = 0;
        let tmp = [];
        for (let j = 0; j < elements.length; j++) {
            sum += circlePer[i + j];
            tmp.push(sum);
        }
        hap.push(tmp)
    }
    console.log(hap) ;
    return
  }
  

  

끝으로 중복없이 모아두기 위해 Set(집합)의 자료형을 사용하자.

집합 : 중복되는 원소 없이, 순서에 상관없는 데이터들 묶음

• 다음과 같이, 중복없이 된 값들이 모여진 것을 확인할 수 있다.

  function solution(elements) {
    const circlePer = [...elements, ...elements]
    const set = new Set() // 집합 자료형 사용
    for (let i = 0; i < elements.length; i++) {
        let sum = 0;
        for (let j = 0; j < elements.length; j++) {
            sum += circlePer[i + j];
            set.add(sum);
        }
    }
    console.log([...set]);
    return
  }
  

  

---

최종 코드

• 최종적으로, 가짓 수를 반환하기 위해 집합의 크기를 반환하자.

function solution(elements) {
    const circlePer = [...elements, ...elements]
    const set = new Set()
    for (let i = 0; i < elements.length; i++) {
        let sum = 0;
        for (let j = 0; j < elements.length; j++) {
            sum += circlePer[i + j];
            set.add(sum);
        }
    }    
    return set.size
 }

---