TIL 240624 - 알고리즘 코드카타 리뷰 - 연속 부분 수열 합의 개수

1. 문제

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

프로그래머스

원형 수열에서 연속하는 부분 수열의 합의 경우의 수를 구하는 문제이다.

 

2. 초기 코드

function solution(elements) {
  elements.push(...elements);
  let acc = [];
  for (let i=0; i<elements.length/2; i++) {
    let sum = 0;
    for (let j = 0; j < (elements.length-1) / 2; j++) {
      sum+=elements[i+j];
      if (!acc.includes(sum)) acc.push(sum);
    }
  }
  return acc.size;     
}

기존 배열을 한번 더 붙여 2번 반복되는 배열을 만들고, 배열을 2중 for문으로 순회하며 각 요소에서부터 1~(요소의 길이)개의 요소들의 합을 acc에 저장하는 형태이다. 이때 중복된 값이 들어가면 안되므로, includes 를 이용하여 이미 포함된 값인지 검사를 하였다.

 

이때, 2중 for문에 또 한번의 순회를 거치는 includes 과정까지 더해져 런타임 에러가 발생하였다.

 

3. 최종 코드

function solution(elements) {
  elements.push(...elements);
  let acc = new Set();
  for (let i=0; i<elements.length/2; i++) {
    let sum = 0;
    for (let j = 0; j < (elements.length-1) / 2; j++) {
      sum+=elements[i+j];
      acc.add(sum);
    }
  }
  return acc.size;
      
}

저장하는 acc 타입을 배열이 아닌 Set으로 바꾸었다. Set은 값을 저장할 때 중복되는 값은 하나의 값으로 처리하기 때문에, 런타임을 줄일 수 있다.