[JS] 연속된 부분 수열의 합

처음에는 dp형식으로, 값을 하나씩 더해 나가면서 합이 맞춰지는 지 확인하고, 합이 맞춰지는 경우 해당 경우의 시작 인덱스와 끝 인덱스로 길이를 파악해서 답을 구하려고 했다.

 

 

function solution(sequence, k) {
    const ary = [... new Array(sequence.length)].fill(0)
    let ret = [0,sequence.length-1]
    let s = 0
    
    for (let i=0 ; i<sequence.length ; i++){
        for(let j=s; j<=i ; j++) {
            ary[j]+=sequence[i]
            if (ary[j] >= k) s = j
            if (ary[j]===k && i-s < ret[1]-ret[0]) ret = [s,i]
        }        
    }
    return ret
}

 

결과 자체는 잘 나왔지만 이중 반복문을 사용하면서 dp를 채워나간거라 시간초과가 나버렸다. 계속 고민하던중 어떤 알고리즘을 써야할지 헷갈려서 인터넷을 검색했는데 투포인터라는 말이 나오자마자 인터넷 창을 닫았다..

 

 

애초에 처음 풀때 시작 인덱스와 끝인덱스를 비교해 나가면서 풀었으면서 투포인터 알고리즘을 까먹고 있었던 것이다.

 

 

아무튼 풀이 방법은 아래와 같다.

 

 

left,right 를 저장할 변수를 정해준다.

 

 

위처럼 정해준 후, L-R 사이의 합을 저장할 변수 sum_ 을 하나 정해준다.

 

 

sum을 비교하면서 sum이 k보다 작으면 숫자를 더해줘야 하므로 R을 +1해주고, 너무크면 L을 +1해주면 된다. k와 같은 값이 나오는 경우에는 L-R 길이를 비교하면서 답을 갱신해주면 된다.

 

 

function solution(sequence, k) {
    let [left,right] = [0,0]
    let sum_ = sequence[0]
    let ret = [0,sequence.length]
    
    while(left < sequence.length){
        if (sum_ < k && right < sequence.length){
            sum_ += sequence[++right]
        }  else if (sum_ === k && right-left < ret[1]-ret[0]){
            ret = [left,right]
            sum_ += sequence[++right]
        } else sum_ -= sequence[left++]
        
        
    }
    return ret
    
}