연속된 부분 수열의 합

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

연속된 부분 수열의 합Lv.2

178870

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

해설

이 함수는 주어진 숫자 배열 sequence에서 합이 k와 같은 연속된 부분 수열을 찾는 문제를 풀기 위한 것입니다. 함수의 반환값은 조건을 만족하는 연속된 부분 수열의 시작과 끝 인덱스를 담은 배열 [startIndex, endIndex]입니다.

  • Name
    startIndex, endIndex 초기화
    Type
    Description

    연속된 부분 수열을 찾기 위해 시작 인덱스(startIndex)와 끝 인덱스(endIndex)를 0으로 초기화합니다.

  • Name
    sum 계산
    Type
    Description

    sum 변수를 이용하여 현재 부분 수열의 합을 계산합니다. 초기에는 첫 번째 요소를 sum에 저장합니다(sequence[0]).

  • Name
    부분 수열 확인
    Type
    Description

    startIndexendIndex를 이용하여 sumk와 같은지 확인합니다. 만약 sumk와 같다면, 현재 부분 수열이 조건을 만족하는 것입니다.

  • Name
    부분 수열 갱신
    Type
    Description

    조건을 만족하는 부분 수열을 찾았을 때, 이전에 찾은 부분 수열(result)보다 길이가 더 작다면 result를 현재 부분 수열의 인덱스로 갱신합니다. 그리고 startIndex를 1 증가시켜서 다음 부분 수열을 확인합니다.

  • Name
    부분 수열 확장 또는 축소
    Type
    Description

    현재 부분 수열의 합(sum)이 k보다 작다면 endIndex를 1 증가시켜서 부분 수열을 확장합니다. 반대로 sumk보다 크다면 startIndex를 1 증가시켜서 부분 수열을 축소합니다.

  • Name
    탐색 종료 조건
    Type
    Description

    startIndexendIndexsequence의 길이를 넘어서지 않도록 하며, 탐색이 끝날 때까지 반복합니다.

  • Name
    결과 반환
    Type
    Description

    조건을 만족하는 가장 짧은 길이의 연속된 부분 수열의 시작과 끝 인덱스를 담은 배열(result)을 반환합니다. 조건을 만족하는 부분 수열이 없을 경우 resultnull이며, 이때는 null을 반환합니다.

연속된 부분 수열의 합

function solution(sequence, k) {
  let startIndex = 0;
  let endIndex = 0;
  let sum = sequence[0];
  let result = null;

  while (startIndex <= endIndex && endIndex < sequence.length) {
    if (sum === k) {
      if (result === null || endIndex - startIndex < result[1] - result[0]) {
        result = [startIndex, endIndex];
      }
      sum -= sequence[startIndex];
      startIndex++;
    } else if (sum < k) {
      endIndex++;
      sum += sequence[endIndex];
    } else {
      sum -= sequence[startIndex];
      startIndex++;
    }
  }
  return result;
}