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

문제

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

접근 방법

합이 k인 연속 구간 중 가장 짧은 구간을 찾고, 길이가 같다면 시작 인덱스가 작은 구간을 선택한다. 최대 100만 개의 원소를 모든 구간으로 비교하면 O(n²)이므로 투 포인터로 탐색한다.

이 풀이가 가능한 핵심 조건은 모든 원소가 양수라는 점이다. 오른쪽 포인터를 늘리면 합이 증가하고, 왼쪽 포인터를 늘리면 합이 감소한다. 음수가 포함된 수열에서는 같은 방식으로 포인터를 이동할 수 없다.

right를 오른쪽으로 한 칸씩 이동하며 값을 더한다. 합이 k보다 큰 동안 왼쪽 값을 빼고 left를 이동한다. 합이 k이면 현재 구간이 후보가 된다.

후보를 모두 저장해 정렬하는 대신 가장 짧은 구간만 유지한다. 길이가 같으면 갱신하지 않는다. left가 감소하지 않으므로 앞서 발견한 후보의 시작 인덱스가 더 작거나 같아 동률 조건도 충족한다.

코드

function solution(sequence, k) {
  let left = 0
  let sum = 0
  let bestStart = 0
  let bestEnd = 0
  let bestLength = Infinity

  for (let right = 0; right < sequence.length; right++) {
    sum += sequence[right]
    while (sum > k && left <= right) {
      sum -= sequence[left]
      left += 1
    }

    const length = right - left + 1
    if (sum === k && length < bestLength) {
      bestStart = left
      bestEnd = right
      bestLength = length
    }
  }

  return [bestStart, bestEnd]
}

복잡도와 경계 조건

원소 수가 n이면 시간은 O(n), 추가 공간은 O(1)이다. 두 포인터가 각각 최대 n번 이동하며, 후보 정렬은 하지 않는다.

길이가 같은 정답이 여러 개인 경우와 원소 하나가 k인 경우를 확인한다. 문제에서 합이 k인 구간의 존재를 보장하므로, 정답이 없는 입력의 반환 규칙은 별도로 정의하지 않았다.