2Level / 연습 문제 / 연속된 부분 수열의 합

문제 설명

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

프로그래머스

 

풀이 방법

이 문제는 인수의 길이를 확인하고 시간 복잡도를 생각해서 이중 for문을 사용하지 않고 풀어야하는 문제라 생각했다.나는 투포인터 알고리즘을 이용해 문제를 풀기로 했다.

 

고려해야 하는 상황은 3가지 이다.1. 부분 수열의 합이 k값보다 작고 오른쪽 포인트가 수열의 끝 인덱스보다 작을 때2. 부분 수열의 합이 k값과 같고 기존 수열의 범위와 비교해서 지금의 범위가 작을 때3. 부분 수열의 합이 k값 보다 크거나 작을 때

 

사실 투포인터 알고리즘에서는 아래와 같이 오른쪽 포인터가 증가하다가

왼쪽 포인터도 같이 증가하며 경우의 수를 확인하는 방식으로 진행했다.

 

코드

const solution = (sequence, k) => {
    let answer = [0, sequence.length];
    let [lp, rp] = [0, 0];
    let sum = sequence[0];
    while(lp < sequence.length){
        if(sum < k && rp < sequence.length){
            sum += sequence[++rp];
        }
        else if(sum === k && rp - lp < answer[1] - answer[0]){
            answer = [lp, rp];
            sum += sequence[++rp];
        }
        else{
            sum -= sequence[lp++];
        }
    }
    return answer;
}