문제를 푸는 기준

연속 부분 배열에서 모든 시작·끝 조합을 만들기 전에 경계를 한 방향으로만 움직일 수 있는지 확인합니다.

핵심 개념

대표 문제

목표 합 이상인 최소 길이

양의 정수 배열 numbers에서 합이 target 이상인 연속 부분 배열의 최소 길이를 반환하세요. 없으면 0을 반환합니다.

함수 시그니처: solution(numbers, target)

제한사항

• numbers의 길이는 1 이상 200,000 이하입니다.
• 모든 원소는 양의 정수입니다.

입출력 예

풀이 설계

1. right를 늘리며 합을 더합니다.
2. 합이 target 이상이면 길이를 갱신합니다.
3. 조건이 유지되는 동안 left 값을 빼며 창을 줄입니다.

JavaScript 풀이

function solution(numbers, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;
  for (let right = 0; right < numbers.length; right += 1) {
    sum += numbers[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= numbers[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(1)
• 핵심 패턴: 오른쪽을 넓히고 조건 만족 시 왼쪽을 줄이는 가변 창
• 경계 사례: 조건을 만족하는 구간이 없으면 0 반환

연습 문제

1. 고정 길이 최대 합

길이 k 구간의 최대 합을 반환하세요.

2. 구간 합 질의

여러 구간 합을 반환하세요.

3. 정렬 배열 두 수 합

target을 만드는 두 값 위치를 반환하세요.

자주 하는 실수

• 음수가 있는 배열에 같은 가변 창을 쓰는 실수
• 창 길이에서 1을 빼먹는 실수
• left 이동 시 합을 빼지 않는 실수
• 정답 없음에 Infinity를 반환하는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• MIT OpenCourseWare 6.006 Introduction to Algorithms 
• MDN Array 
• 프로그래머스 코딩테스트 고득점 Kit