[프로그래머스] 연속된 부분 수열의 합 문제풀이 JS

sequence를 탐색하는데 투포인터로

시작점부터 끝점의 합이 k가 되는 지점을 확인한다.

합이 k가 되는 지점일 경우엔 answer을 비교해 현재 start와 end의 길이가 더 짧다면

answer와 sum, start, end를 업데이트한다.

합이 k보다 클때는 start지점의 값을 sum에서 빼고 start를 1증가한다.

합이 k보다 작을 때는 end를 1증가하고 sum에 해당값을 더한다.

이 과정을 sequence의 길이만큼 반복하면

부분수열의 합이 k인 경우는 무조건 있으므로,

answer에는 합이 k이면서 길이가 가장 짧으면서 제일 처음 나오는 index의 시작점과 끝점이 저장되어 있다.

 

function solution(sequence, k) {
  let answer = [0, 1000000]
  let start = 0,
    end = 0,
    sum = sequence[0]
  while (end < sequence.length) {
    if (sum === k) {
      if (answer[1] - answer[0] > end - start) {
        answer = [start, end]
      }
      sum -= sequence[start++]
      sum += sequence[++end]
    } else if (sum > k) {
      sum -= sequence[start++]
    } else {
      sum += sequence[++end]
    }
  }
  return answer
}

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

프로그래머스