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

문제 설명 

원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 리턴하도록 solution 함수 완성하라. 

원형 수열이란 처음과 끝이 연결되어 있는 수열을 말한다. 

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

프로그래머스

문제 풀이

처음에 접근하기를 원형 수열이니 배열을 뒤로 이어 붙여서 원본 배열의 원소 갯수만큼 slice를 해서 해당 slice 배열의 합의 집합을 구하면 되지 않을까 생각했다. 

즉 핵심은

1. 배열을 이어 붙인다. 

2. slice 후 해당 배열의 합의 집합을 구한다. 

 

그래서 작성한 첫 코드 

function solution(elem) {
    let len=elem.length
    elem=elem.concat(elem)
    let result=[]
    for(let i=1;i<=len;i++){
        for(let j=0;j<len;j++){
            if(j+i>=elem.length)continue
            if(j>=len)continue
            let new_arr=elem.slice(j,j+i)
            let sum=new_arr.reduce((acc,i)=>acc+i)
            if(!result.includes(sum))result.push(sum)
        }
    }
    return result.length
}

시간초과가 나왔다. 

마지막 부분에서 includes를 판단하며 원소를 추가해준게 시간을 잡아먹은 것 같아서 set을 사용하여 아래의 풀이를 작성했다. 

function solution(elem) {
    let len=elem.length
    elem=elem.concat(elem)
    let result=new Set()
    for(let i=1;i<=len;i++){
        for(let j=0;j<len;j++){
            if(j+i>=elem.length)continue
            if(j>=len)continue
            let new_arr=elem.slice(j,j+i)
            let sum=new_arr.reduce((acc,i)=>acc+i)
            result.add(sum)
        }
    }
    return result.size
}

답은 통과!

Array.prototype.includes의 시간 복잡도는 O(n)이다. 

집합에 원소를 추가, 삭제하는 것은 O(1)

set.has로 검색하는 것도 O(1)이다.