[프로그래머스] Lv2. 연속된 부분 수열의 합- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 연속된 부분 수열의 합

문제

제한사항

📌 내가 생각한 풀이

제한사항을 보고 5<= sequence의 길이 <= 1,000,000이므로 시간초과를 피하는 방식으로 문제를 풀어야겠다고 생각했다. 이중 포인터를 이용하여, 합보다 작으면 기존 sequence[p2]값을 더한다음 p2를 증가시키고, 합보다 크면 기존 sequence[p1]값을 빼고 p1을 증가시키자. 또한 sum===k일 경우엔 p2값을 더해주어서 다시 시작한다.

function solution(sequence, k) {
    var answer = [];
    let p1 = 0;
    let p2 = 1;
    let sum = sequence[p1];
    let stack = [];
    while(p2 <= sequence.length){
        if(sum < k){
            sum+=sequence[p2];
            p2++;
        }else if(sum >k){
            sum-=sequence[p1];
            p1++;
        }else{
            stack.push([p1,p2-1])
            sum+=sequence[p2];
            p2++;
        }   
    }
    stack.sort((a,b)=>{
        if(a[1]-a[0] !== b[1]-b[0] ){
            return a[1]-a[0] - b[1]-b[0] > 0 ? 1 : -1
        }
    })
    return (stack[0])
}

📌 느낀점

비교적 문제를 해결하는데 15분정도 걸리는 쉬운 문제였다. 시간복잡도를 간단하게 하기 위해서 sum값을 갱신될때마다 더해주지 않고, 인덱스를 이용하여 기존값에서 더하고 뺌으로 연산을 확실히 줄일 수 있는 방법을 알고있어서 쉽게 풀었다.