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

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

프로그래머스

제한사항

5 ≤ sequence의 길이 ≤ 1,000,000
1 ≤ sequence의 원소 ≤ 1,000
sequence는 비내림차순으로 정렬되어 있습니다.
5 ≤ k ≤ 1,000,000,000
k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

 

제한사항을 통해 모든 부분 수열을 구해서 풀이하는 것이 어렵다고 판단했지만 배열의 큰 수부터 거꾸로 하는 방법으로 구현해서 시간초과 발생 확인

 

DP 방식으로 아이디어를 생각해 봤지만 떠오르지 않았음. 대신 부분 수열의 합에 대한 특징을 이용하여 아이디어가 떠오름

 

k보다 크거나 같을 때까지 endIndex를 더해주며 Index를 늘려가고 만약 해당 조건이 된다면 앞의 값을 당겨오면서 endIndex가 끝까지 갔을 때까지 계산하도록 함

• endIndex와 startIndex가 같지 않을 때 endIndex가 끝까지 갔다면 이후 부분 수열은 해답이 될 수 없음
• 연속된 수열의 합이기 때문에 현재 덧셈의 합이 k보다 크다면 현재 endIndex 이후 부분수열은 해답이 될 수 없음

연속된 부분 수열의 합에 대한 특징을 알았다면 쉽게 구현할 수 있는 문제였음.

 

여러 알고리즘을 고민하며 문제를 해결하다 보니 본질에서 벗어나 생각하게 된 것 같음. 직관적으로 문제의 본질을 파악하는 연습을 해야 함.

function solution(sequence, k) {
    var answer = [];
    
    let startIndex = 0;
    let endIndex = 0;
    let sum = sequence[0];
    
    while(endIndex < sequence.length){
        if(sum >= k){
            if(sum == k){
                if(answer.length < 1){
                    answer = [startIndex, endIndex];
                } else {
                    const answerLength = answer[1] - answer[0];
                    const length = endIndex - startIndex;
                    if(length < answerLength){
                        answer = [startIndex, endIndex];
                    }
                }
                
                const frontVal = sequence[startIndex];
                sum -= frontVal;
                startIndex++;

                continue;
            }
            
            while(sum > k){
                const frontVal = sequence[startIndex];
                sum -= frontVal;
                startIndex++;
            }
            
        } else {
            endIndex++;
            const curr = sequence[endIndex];
            sum += curr;
        }        
    }
    
    return answer;
}