[Programmers] 연속된 부분 수열의 합 - Javascript

INDEX

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

프로그래머스

 

Solution

수열을 순회하면서 연속된 수열의 합이 K인 원소의 인덱스를 찾으면 됩니다.

 

예제로 주어진 sequence를 도식화해 보면 다음과 같습니다.

startIdx = 0, endIdx = 0

연속된 수열의 합을 구하기 위해선 처음 INDEX 와 끝 INDEX가 필요합니다.

let startIdx = 0;
let endIdx = 0;
let answer = [0, 1000000]; //끝 INDEX와 처음 INDEX의 차이가 작을수록 정답이 되기 때문에 answer 은 최대값으로 초기화
let sum = sequence[0]; //현재는 1

이 배열은 비내림차순 즉, 올림차순이라고 생각하면 수열의 합이 K보다 작으면 endIdx를 오른쪽으로 밀고 K보다 크면 startIdx를 오른쪽으로 밀면 됩니다. 왜냐하면 endIdx를 오른쪽으로 밀면 startIdx부터 endIdx까지의 수열의 합이 더 커질 것이고 startIdx를 오른쪽으로 밀면 수열의 합이 작아지기 때문입니다.

 

현재는 합이 1이기 때문에 K인 7보다 작습니다. 따라서 endIdx 를 오른쪽으로 이동합니다.

if(sum < k){
    endIdx++;
    sum += sequence[endIdx];
}

startIdx = 0, endIdx = 1

합이 3이기 때문에 endIdx를 오른쪽으로 이동합니다.

startIdx=0, endIdx = 2

여전히 합이 6이므로 K보다 작습니다. endIdx 를 오른쪽으로 이동합니다.

startIdx=0, endIdx=3

이번엔 합이 K보다 작습니다. startIdx를 오른쪽으로 이동합니다.

if(sum > k){
    sum -= sequence[startIdx]
    startIdx++;
}

startIdx=1, endIdx=3

합이 K가 되었습니다. 이제 startIdx 와 endIdx를 정답에 담습니다. 

if(sum === k){
    answer = answer[1]- answer[0] > endIdx - startIdx ? [startIdx, endIdx] : answer;
    endIdx++;
    sum += sequence[endIdx];
}

 

이런 식으로 endIdx 가 끝에 도달할 때까지 해주면 됩니다.

 

전체코드

function solution(sequence, k) {
    let startIdx = 0;
    let endIdx = 0;
    let answer = [0, 1000000];
    let sum = sequence[0];    
    while(endIdx !== sequence.length){
        if(sequence[endIdx] === k) return [endIdx, endIdx]
        if(sum === k){
            answer = answer[1]- answer[0] > endIdx - startIdx ? [startIdx, endIdx] : answer;
            endIdx++;
            sum += sequence[endIdx];
        }
        else if(sum < k){
            endIdx++;
            sum += sequence[endIdx];
        }
        else if(sum > k){
            sum -= sequence[startIdx]
            startIdx++;
        }
    }
    return answer;
}