본문으로 건너뛰기

0709

프로그래머스 - 연속된 부분 수열의 합​

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

접근 방법​

비내림차순으로 정렬된 수열의 부분 수열 중, 그 합이 k이면서 길이가 짧고, 시작 인덱스가 작은 수열을 찾아서 해당 수열의 시작과 끝 인덱스를 배열에 담아 반환하는 문제이다.

수열 sequence의 최대 길이가 100만으로 매우 길기 때문에, 단순 이중 반복문으로 수열을 완전 탐색하면 $$O(n^2)$$의 시간 복잡도를 갖게 되어 시간 초과가 날 확률이 크다.

따라서 이 문제는 두 개의 포인터를 활용해서 선형적인 탐색을 통해 수열을 찾아야 한다. 이른바 투 포인터 유형이다.

풀이 방법은 다음과 같다.

  1. 처음에 시작(start)과 끝(end)은 인덱스 0을 가리킨다.
  2. 부분합을 계산해서 k와 같다면 두 포인터의 인덱스를 기록한다.
  3. 부분합이 k보다 작거나 같다면, end를 1 증가시킨다.
  4. 부분합이 m보다 크다면, start를 1 증가시킨다.
  5. 모든 경우를 확인할 때 까지 단계 2 - 4를 반복한다.

Implementation​

  • 수열의 길이, 부분 수열을 기록할 배열, 부분합, end 포인터를 선언한다.
  • start 포인터를 end 포인터에 점점 가깝게 만들면서 부분합을 찾는다.
  • 우선 end를 가능한 만큼 이동시킨 뒤에 (이동하면서 부분합에 end가 가리키는 값을 더해감)
  • 부분합이 k라면, start와 end 인덱스를 기록한다.
  • 그리고 end가 가리키는 값은 이미 더해진 상태이므로, start가 가리키는 값은 부분합에서 빼준다.
  • 마지막으로 기록한 부분 수열들을 정렬하는데, 두 인덱스 차이가 작은 순으로 정렬한다.
  • 정렬된 배열에서 첫번째 부분 수열을 가져오면 정답 판정을 받을 수 있다.

Code​

function solution(sequence, k) {
    const n = sequence.length;
    const subSequence = [];
    let subSum = 0;
    let end = 0;

    for (let start = 0; start < n; start++) {
        while (subSum < k && end < n) {
            subSum += sequence[end];
            end += 1;
        }
        if (subSum === k) {
            subSequence.push([start, end - 1]);
        }
        subSum -= sequence[start];
    }
    subSequence.sort((a, b) => {
        return (a[1] - a[0]) - (b[1] - b[0]);
    });
    return subSequence[0];