[Javascript] 프로그래머스 - 연속된 부분

문제 설명

비내림차순으로 정렬된 수열에서 다음 조건을 만족하는 부분 수열을 찾는 문제입니다.

• 부분 수열은 주어진 수열에서 연속된 원소들로 이루어져야 합니다.
• 부분 수열의 합은 k여야 합니다.
• 합이 k인 부분 수열이 여러 개인 경우:
  1. 길이가 짧은 수열을 우선적으로 선택합니다.
  2. 길이가 같은 경우 시작 인덱스가 작은 수열을 선택합니다.

---

제한사항

1. 수열의 길이: 5 ≤ sequence.length ≤ 1,000,000
2. 원소의 값: 1 ≤ sequence[i] ≤ 1,000
3. 부분 수열의 합: 5 ≤ k ≤ 1,000,000,000
4. k는 항상 수열의 부분 수열로 만들 수 있는 값입니다.

---

해결 방법

알고리즘: 투 포인터

1. 포인터 초기화
   • 왼쪽 포인터(left)와 오른쪽 포인터(right)를 배열의 첫 번째 원소(인덱스 0)로 초기화합니다.
   • 현재 구간의 합(num)을 배열의 첫 번째 원소 값으로 설정합니다.
2. 구간 합 조정
   • 구간 합이 k보다 작으면 오른쪽 포인터를 이동하여 구간을 확장합니다.
   • 구간 합이 k보다 크면 왼쪽 포인터를 이동하여 구간을 축소합니다.
   • 합이 k와 같으면:
     1. 현재 구간의 길이가 이전 결과보다 짧은 경우, 새로운 결과로 갱신합니다.
     2. 길이가 같을 경우, 시작 인덱스가 더 작은 구간을 우선 선택합니다.
3. 결과 반환
   • 조건을 만족하는 최소 길이의 구간의 시작점과 끝점을 반환합니다.

---

시간 복잡도

1. 투 포인터 반복:
   • 각 포인터는 배열을 한 번만 순회하므로 O(n), n은 수열의 길이
2. 총 복잡도: O(n)

---

구현 코드

function solution(sequence, k) {
  let left = 0;
  let right = 0;
  let num = sequence[0];
  let answerLeft = 0;
  let answerRight = 0;
  let answerSize = Infinity;

  while (right < sequence.length) {
    if (num < k) {
      ++right;
      num += sequence[right];
    } else if (num > k) {
      num -= sequence[left];
      ++left;
    } else if (num === k) {
      if (right - left < answerSize) {
        answerLeft = left;
        answerRight = right;
        answerSize = answerRight - answerLeft;
      }
      num -= sequence[left];
      ++left;
      ++right;
      num += sequence[right];
    }
  }

  return [answerLeft, answerRight];
}