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

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

🤔 해결방법

1. elements의 길이만큼 요소들을 차례로 묶어 더한다. 만약 인덱스가 배열의 길이를 넘어가면 인덱스를 순환시킨다.

2. 중복 아닌 것만 result에 추가하고 result의 사이즈를 출력한다.

 

🔑 풀이

function solution(elements) {
    const result = new Set();

    //i는 묶을 요소의 개수
    for (let i = 1; i <= elements.length; i++) {
      //j는 묶을 요소들의 시작 인덱스
      for (let j = 0; j < elements.length; j++) {
        let sum = 0;

        //k는 더해질 요소들의 인덱스
        for (let k = 0; k < i; k++) {
          //인덱스가 배열의 길이를 넘어갈 경우 인덱스 순환
          sum += elements[(j + k) % elements.length];
        }
        result.add(sum); //중복 아닌 것만 알아서 추가
      }
    }

    return result.size;
  }

 

😭 삽질

처음에 다음과 같은 코드를 짰다.

function solution(elements) {
    let result = [];

    //elements의 길이만큼 반복
    for (let i = 1; i <= elements.length; i++) {

      //i번 배열 복사
      const newElements = [...elements];
      for (let j = 1; j < i; j++) {
        newElements.push(...elements);
      }

      //i개씩 요소를 더하여 중복 확인 후 추가
      for (let z = 0; z < newElements.length; z++) {
        let sum = 0;
        let array = newElements.slice(z, z + i);
        array.forEach((e) => {
          sum += e;
        });
        if (!result.includes(sum)) result.push(sum);
      }
    }

    return result.length;
  }

 

elements의 요소들을 i번 복사하여 넣은 newElements에서 i개씩 요소를 더하고 중복 확인 후 result에 추가하는 코드다.

단순하게 elements를 i번 복사하여 newElements를 만드는 것부터 elements의 길이가 길어지고 i의 값이 커지면 당연히 시간초과가 나올 것을 예상했다.😂

그래도 호옥시나 하는 마음에 그대로 제출해봤는데 역시나 1번 테스트케이스 빼고는 나머지 모두 시간초과가 나왔다.

그래서 인덱스가 배열의 길이를 넘어갈 경우 %를 사용하여 인덱스를 순환시키도록 수정했다.

 

function solution(elements) {
    let result = [];

    //elements의 길이만큼 반복
    for (let i = 1; i <= elements.length; i++) {
      for (let j = 0; j < elements.length; j++) {
        let sum = 0;

        //i개씩 더함
        for (let k = 0; k < i; k++) {
          sum += elements[(j + k) % elements.length];
        }

        //중복이 없으면 추가
        if (!result.includes(sum)) result.push(sum);
      }
    }

    return result.length;
  }

 

위와 같이 수정 후 제출했더니 테스트케이스 4번까지는 통과했으나 나머지는 여전히 시간초과였다.

그리고 삼중 for문이 되다보니 헷갈려서 예시로 i가 2,3일 때만 직접 공책에 쓰며 변수의 변화를 체크했다.😂

 

만약 result를 처음에 배열 대신에 중복을 허용하지 않는 Set으로 선언한다면 if문 필요없이 그냥 result에 알아서 중복이 안된 것만 들어가게 되므로 시간이 조금 단축될 듯 했다.

그래서 result를 Set으로, push를 add로, length를 size로 바꿔줬다.

 

function solution(elements) {
    const result = new Set();

    //i는 묶을 요소의 개수
    for (let i = 1; i <= elements.length; i++) {
      //j는 묶을 요소들의 시작 인덱스
      for (let j = 0; j < elements.length; j++) {
        let sum = 0;

        //k는 더해질 요소들의 인덱스
        for (let k = 0; k < i; k++) {
          //인덱스가 배열의 길이를 넘어갈 경우 인덱스 순환
          sum += elements[(j + k) % elements.length];
        }
        result.add(sum); //중복 아닌 것만 알아서 추가
      }
    }

    return result.size;
  }

 

다행히 모든 테스트 케이스를 통과했다.😀

하지만 삼중for문이라 가독성이 떨어진다는 단점이 있는 듯 하다....😥