[Programmers] 연속 부분 수열 합의 개수 - JavaScript

Joosi_Cool·2023년 3월 1일
0

Programmers

목록 보기
25/98
post-thumbnail
post-custom-banner

문제설명




설계 과정

우선, 원순열을 위해 elements을 두개를 이어주는 배열을 만든다. -> element
fisrt 라는 변수 생성 => 이는 합을 구할 원소 개수와 관련된 값

  • elements의 길이만큼 아래 과정을 반복
  1. element를 한번 쭉 돈다.
  2. 돌때, fisrt만큼 자른다.
  3. 자른 배열의 합을 구함
  4. 합 배열에 이것이 존재하지 않는다면 push

  • 마지막에 합 배열의 길이를 리턴


초기 코드

function solution(elements) {
    var answer = [];
    var first = 1;
    var length = elements.length;
    const element = [...elements,...elements];
    var sum;
    
    for(var k =0;k<length;k++){
        for(var i = 0;i<length;i++){
            sum=element.slice(i,i+first).reduce((a,b)=>(a+b));
            if(answer.indexOf(sum)===-1){
                answer.push(sum);
            }
        }  
        first++;
    }     
    return answer.length;
}

 console.log(solution([7,9,1,1,4]));


결과

결과는 처참하게 시간초과가 나왔다.
시간 초과나 나온 이유는 for문 안에 for문이 있는 이중for문이며, 또 안에 배열의 합을 구할때 시간 복잡도가 쓰인다. 너무 복잡하다.... 이를 해결할 코드가 필요하다.



개선 코드

function solution(elements) {
    var answer = [];
    var first = 1;
    var length = elements.length;
    const element = [...elements,...elements];
    for(var k =0;k<length;k++){
        for(var i = 0;i<length;i++){
            answer.push(element.slice(i,i+first).reduce((a,b)=>(a+b)));
        }  
        first++;
    }     
    const result = [...new Set(answer)];
    return result.length;
}

어떤식으로 코드를 개선시킬지 고민하던중, 중복배열을 찾기 위해 indexOf를 계속해서 확인하는 것이 너무 불필요한 과정이라고 생각이 들었다. 그래서 마지막에 한꺼번에 하는 효율적인 방법이 뭐가 있을지 공부했고, Set에 대해 알게 되었다. 이를 적극 활용하니 문제를 풀어낼 수 있었다.

결과

profile
집돌이 FE개발자의 노트
post-custom-banner

0개의 댓글