[슬라이딩 윈도우] 연속된 부분 수열의 합 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

[문제 간단 요약]

 

• 양의 정수로 이루어진 배열 sequence와 정수 k가 주어짐.
• 합이 정확히 k가 되는 연속 부분 수열 [s, e]를 찾아야 함.
• 답이 여러 개라면 길이가 가장 짧은 구간을 선택.
• 반환 형식: [시작 인덱스, 끝 인덱스].

 

 

[문제 해결 방안]

• 모든 수가 양수이므로, 투 포인터(슬라이딩 윈도우) 기법을 사용 가능.
• 두 포인터 s, e를 이용해 구간의 합 ssum을 유지하면서 탐색:
  1. ssum < k → 오른쪽 포인터 확장 (e += 1)
  2. ssum >= k → 왼쪽 포인터 이동 (s += 1)
• ssum == k인 순간마다 현재 구간 길이가 기존 답보다 짧으면 답 갱신.

[문제 해결 코드 - python]

def solution(sequence, k):
    s = 0
    e = 0
    answer = [0, len(sequence)]
    ssum = sequence[0]

    while True:
        if ssum < k:
            e += 1
            if e == len(sequence): break
            ssum += sequence[e]
        else:
            if ssum == k:
                if e-s < answer[1]-answer[0]:
                    answer = [s, e]
            ssum -= sequence[s]
            s += 1
    return answer

 

 

[문제 해결 코드 - javascript]

function solution(sequence, k) {
  let s = 0, e = 0;
  let answer = [0, sequence.length];
  let ssum = sequence[0];

  while (true) {
    if (ssum < k) {
      e++;
      if (e === sequence.length) break;
      ssum += sequence[e];
    } else {
      if (ssum === k) {
        if (e - s < answer[1] - answer[0]) {
          answer = [s, e];
        }
      }
      ssum -= sequence[s];
      s++;
    }
  }
  return answer;
}

 

[코드 개선점]

• 투 포인터 최적화 덕분에 전체 탐색을 O(n) 안에 처리할 수 있음.
  • • 현재 코드로도 문제 요구사항을 충족하지만, 추가로 고려할 수 있는 부분:
      • 동일 길이 구간이 여러 개일 때 시작 인덱스가 작은 구간을 선택하는 조건(문제 조건에 따라 필요할 수도 있음).
      • while True 대신 while e < len(sequence) 형태로 작성하면 조금 더 직관적임.
      • answer 초기값을 [0, len(sequence)]로 잡아두는 아이디어가 깔끔함.