[프로그래머스] Level2 - 연속된 부분 수열의 합(Javascript)

프로그래머스

▶ 문제 요약

1. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 한다. 

2. 부분 수열의 합은 k이다.

3. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾는다. 

4. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾는다. 

 

 

 

▶ 실패 코드

function solution(sequence, k) {
    let answer = [];
    let temp = [];
    let sum = 0;
    
    for (let i = 0; i < sequence.length; i++) {
        temp.push([sequence[i], i]);
        sum += sequence[i];
        
        while (sum > k) {
            sum -= temp[0][0];
            temp.shift();
        }
        
        if (sum === k) {
            answer.push([temp[0][1], temp[temp.length-1][1], temp.length]);
            sum -= temp[0][0];
            temp.shift();
        }
    }
    
    answer.sort((a, b) => a[2] - b[2]);
    
    let result = answer[0];
    return [result[0], result[1]];
}

▶ 실패 이유

1. 일단 위 코드의 시간복잡도를 보면 배열을 한 번 훑는 작업의 시간 복잡도는 O(N)이다.

2. answer을 정렬하는 작업에서 sort()함수 쓰는데 퀵소트를 기반을 하기 때문에 평균복잡도 n log n 복잡도를 가진다. 그러나 최악의 경우 n^2가 된다.

3. shift() 연산은 O(n)을 가지기 때문에 while 루프 내부의 시간 복잡도는 실제로 O(n ^2)가 된다.

4. 따라서 주어진 배열의 크기가 1000000이면 시간초과가 난다.

 

 

 

 

 

▶ 정답 코드

function solution(sequence, k) {
	let answer = [];
    let start = 0, end = 0, sum = 0;
    let minLen = Infinity;
    
    // end가 주어진 배열의 크기보다 작거나 같을 때까지 돌면서
    while (end <= sequence.length) {
        // 합이 k보다 작으면
        if (sum < k) {
           // 배열 중에서 end에 해당하는 값을 더해주고 후위증가한다. 
           sum += sequence[end++];
        // 만약 합이 k보다 크면   
        } else (sum > k) {
           // 배열 중에서 start에 해당하는 값을 빼주고 후위증가한다.
           sum -= sequence[start++]; 
        // 같으면   
        } else (sum === k) {
           // 길이가 짧은 수열을 찾기
           if (end - start < minLen) {
              // 가장 짧은 수열 업데이트
              minLength = end - start;
              // 결과값 담기
              result = [start, end-1];
           }
           // 배열 중에서 start에 해당하는 값을 빼주고 후위증가한다.
           sum -= sequence[start++];
        }
    
    }
    
    return result




}

 

▶ 풀이 과정

1. 슬라이딩 윈도우 알고리즘을 활용했다. 배열이나 문자열 같은 선형 구조에서 요소의 일정 범위값을 비교할때 이용하면 유용한 방법이다. 투 포인터 패턴과 유사하다. 왼쪽 포인터와 오른쪽 포인터를 조정하는 방식으로 구현하는데 배열을 고정시키기 때문에 효율적이다. 주로 최대/최소값, 평균값 또는 해당 범위 내에서 특정 조건을 충족하는 값을 찾는 문제에 사용된다. 

 

* 슬라이딩 윈도우 알고리즘 사용 일반적인 자바스크립트 구현 방법

let arr = [...];  // 주어진 배열
let windowSize = ...;  // 윈도우 크기
let windowSum = 0;  // 윈도우 내의 합

// 윈도우 초기화
for (let i = 0; i < windowSize; i++) {
    windowSum += arr[i];
}

// 윈도우를 배열의 오른쪽으로 슬라이드
for (let i = windowSize; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - windowSize];
    // 여기서 windowSum은 윈도우 내의 합을 나타냄
}

// 필요에 따라 이후에 windowSum을 이용해 처리

 

2. 코드 실행과정을 통해서 이해해보자.

• 초기 설정: start = 0, end = 0, sum = 0, minLength = Infinity, result = []
• sequence = [1, 1, 1, 2, 3, 4, 5]이고, k = 5.

1. 첫 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행. sum = 1, end = 1
2. 두 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행. sum = 2, end = 2
3. 세 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행. sum = 3, end = 3
4. 네 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행. sum = 5, end = 4
   • 이제 sum === k이므로, if (end - start < minLength)를 확인. minLength는 무한대이므로, result = [start, end - 1]를 실행 result = [0, 3]
   • 그리고 sum -= sequence[start++]를 실행. sum = 4, start = 1
5. 다섯 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행. sum = 7, end = 5
   • sum > k이므로, sum -= sequence[start++]를 실행. sum = 6, start = 2
6. 여섯 번째 반복:
   • sum > k이므로, sum -= sequence[start++]를 실행. sum = 5, start = 3
   • 이제 sum === k이므로, if (end - start < minLength)를 확인. 그러나 end - start는 2이고 minLength는 4이므로, result는 변경돼서 result = [3, 4]
   • 그리고 sum -= sequence[start++]를 실행합니다. sum = 3, start = 4
7. 일곱 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행합니다. sum = 7, end = 6
   • sum > k이므로, sum -= sequence[start++]를 실행합니다. sum = 4, start = 5
8. 여덟 번째 반복:
   • sum < k이므로, sum += sequence[end++]를 실행합니다. sum = 9, end = 7
   • sum > k이므로, sum -= sequence[start++]를 실행합니다. sum = 5, start = 6
   • 이제 sum === k이므로, if (end - start < minLength)를 확인합니다. 그러나 end - start는 1이고 minLength는 4이므로
   • result는 변경되서 result = [6, 6]