문제

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한 사항

5 ≤ sequence의 길이 ≤ 1,000,000

• 1 ≤ sequence의 원소 ≤ 1,000
• sequence는 비내림차순으로 정렬되어 있습니다.

5 ≤ k ≤ 1,000,000,000

• k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

입력

sequence : [1, 2, 3, 4, 5]
k : 7

출력

[2, 3]

내가 했던 풀이 방법

1. 가장 짧은 수열을 저장할 배열 minSequence와 정답을 출력할 배열을 초기화해준다. (minSequence는 굳이 없어도 풀이에 지장은 없다.)
2. start와 sum을 0으로 초기화해준다. 여기서 start는 수열의 시작부분을 의미하고, sum은 수열의 시작부분부터 현재까지의 sum을 의미한다.
3. sequence를 순차적으로 순회하면서 sum에 현재 요소를 더해준다. 만약 sum이 k보다 크다면, sum에서 시작부분부터 제거해준다. 이때, start가 i보다 커지면 안 되므로 start의 값에 유의한다.
4. 3번이 끝난 뒤에 sum이 k와 같고, 현재까지 가장 짧은 배열보다 길이가 더 짧은 경우 (+ 현재까지 조건에 맞는 배열을 찾지 못한 경우) minSequence를 start부터 i까지의 배열로 저장하고, answer를 [start, i]로 저장한다.
5. 모든 연산이 끝난 뒤 answer를 반환한다.

코드

function solution(sequence, k) {
    let minSequence = [];
    let answer = [];
    
    let start = 0;
    let sum = 0;
    for(let i=0; i<sequence.length; i++) {
        sum += sequence[i];
         while (sum > k && start <= i) {
            sum -= sequence[start++];
        }
        
        if(sum===k) {
            if(minSequence.length===0 || minSequence.length>i-start+1) {
                minSequence = sequence.slice(start, i+1);
                answer = [start, i];
            }
        } 
        
    }
    return answer;
}

회고

당연하게 투포인터겠거니 하고 2중 for문으로 접근했다가 바로 제한사항을 보고 2중 for문은 절대 안 될 것 같다 싶어서 바로 생각을 다시 했다. 일부 수열만을 가져오는 게 아니고 연속된 수열이기 때문에 start 부분만 고정시키고 index를 이동시키면서 sum을 벗어날 때마다 start의 위치를 오른쪽으로 옮기면 되겠구나 싶었다. 이런 문제를 풀어본 것..? 같아서 금방 떠올랐다.