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

연속된 부분 수열의 합 — 슬라이딩 윈도우 방식으로 완전하게 설명

문제 핵심 요약

우리가 해결해야 할 문제는 다음과 같습니다.

어떤 정수 수열이 주어졌을 때, 그 안에서 연속된 일부 구간을 선택해서 그 안의 숫자들을 모두 더했을 때, 그 합이 정확히 k가 되는 구간을 찾는 것입니다.

단, 조건이 아주 중요합니다.

• 합이 k인 구간이 여러 개 있다면, 가장 짧은 구간을 선택합니다.
• 길이까지 같은 구간이 여러 개 있을 경우, 가장 앞쪽에 있는 구간을 선택합니다.

즉, 우리는 단순히 "합이 k"인 구간만 찾는 것이 아니라, 조건을 만족하는 '최적의 구간'을 정확히 하나만 골라야 합니다.

예제 하나로 전체 문제를 시각적으로 파악해보기

예를 들어 sequence = [1, 1, 1, 2, 3, 4, 5], k = 5라고 해보겠습니다. 이 배열에서 합이 5가 되는 연속된 구간은 다음과 같습니다.

• [1, 1, 1, 2] → 인덱스 [0, 3]
• [2, 3] → 인덱스 [3, 4]
• [5] → 인덱스 [6, 6]

이 중에서 가장 짧은 구간은 [5]입니다. 인덱스는 [6, 6]입니다. 그래서 정답은 [6, 6]이 됩니다.

이 예시는 문제 조건을 잘 반영하고 있으며, 우리가 단순히 합만 맞추는 게 아니라 “짧은 길이 + 앞쪽 우선”이라는 기준을 함께 고려해야 한다는 점을 보여줍니다.

핵심 아이디어: 슬라이딩 윈도우 (투 포인터)

이제 본격적으로 문제를 풀기 위한 핵심 개념을 설명하겠습니다. 이 문제에서는 흔히 말하는 슬라이딩 윈도우 기법, 또는 투 포인터 기법을 사용합니다.

그 이유는 다음과 같습니다.

• 배열은 정렬되어 있지만, 그게 핵심은 아닙니다.
• 배열의 모든 수는 양의 정수입니다.
• 양의 정수이기 때문에, 더하면 커지고, 빼면 작아진다는 방향성이 명확합니다.

이 “방향성이 명확하다”는 것은, 포인터를 앞쪽으로만 움직이면서도 합을 효율적으로 관리할 수 있다는 뜻입니다.

슬라이딩 윈도우를 상자에 비유해보기

이제 이 방법을 이해하기 쉽게 설명해보겠습니다. 배열 위에 투명한 상자 하나가 있다고 상상해보세요. 이 상자는 두 개의 경계로 구성되어 있습니다.

• 왼쪽 경계: start
• 오른쪽 경계: end

상자는 start부터 end-1까지의 원소를 포함합니다. 즉, [start, end) 구간입니다. 오른쪽 끝인 end는 포함되지 않습니다.

예를 들어 start=2, end=5라면 포함되는 숫자는 인덱스 2, 3, 4의 값입니다.

이 상자를 통해 무엇을 할 수 있느냐? 상자 안의 숫자들의 합(sum)을 구할 수 있고, 이 합이 k와 같아지도록 상자의 크기나 위치를 바꾸는 것이 우리가 해야 할 일입니다.

합이 k보다 작거나, 같거나, 크면 무엇을 해야 하나?

우리는 지금 이 "상자"를 움직이면서 합을 관리합니다. 그때마다 합(sum)과 목표값 k를 비교하게 됩니다.

각 상황에 따라 다음과 같은 행동을 합니다.

① sum < k → 오른쪽을 확장

현재 합이 부족합니다. → 상자 오른쪽을 한 칸 더 넓혀서(end += 1), 숫자를 하나 더 담습니다.

• 예: sum = 3, k = 5 → 부족함 → sequence[end]를 더하고 end += 1

② sum > k → 왼쪽을 줄이기

합이 너무 큽니다. → 상자 왼쪽을 줄입니다. 즉, sequence[start]를 빼고 start += 1 합니다.

• 예: sum = 9, k = 5 → 넘침 → sequence[start]를 빼고 start += 1

③ sum == k → 후보 기록 + 왼쪽 줄이기

합이 정확히 k입니다. → 현재 구간 [start, end-1]을 정답 후보로 기록합니다. → 이후에도 더 짧은 구간이 있을 수 있으므로, 왼쪽을 한 칸 줄여서 탐색을 계속합니다.

이 과정이 반복되며, 모든 가능한 후보 중에서

• 가장 짧고
• 같으면 앞쪽인

최적의 구간이 선택됩니다.

실제 알고리즘 흐름 요약

이제 위 설명을 정리해서 실제 코드 흐름처럼 정리해보면 아래와 같습니다.

1. start, end, sum 초기화 → 모두 0
2. while 루프 시작 (end <= len(sequence))
• 현재 sum과 k 비교
• 작으면 → sum += sequence[end], end += 1
• 크면 → sum -= sequence[start], start += 1
• 같으면
• 길이 비교 후 최적 구간 갱신
• sum -= sequence[start], start += 1
3. 최종적으로 남은 구간 반환

시각적인 예시로 흐름 정리

sequence = [1, 1, 1, 2, 3, 4, 5], k = 5

초기: start=0, end=0, sum=0

1. sum < k → end=1, sum=1  
2. sum < k → end=2, sum=2  
3. sum < k → end=3, sum=3  
4. sum < k → end=4, sum=5 → 기록([0,3])  
5. sum == k → start=1, sum=4  
6. sum < k → end=5, sum=7  
7. sum > k → start=2, sum=6  
8. sum > k → start=3, sum=5 → 기록([3,4])  
9. sum == k → start=4, sum=3  
10. sum < k → end=6, sum=7  
11. sum > k → start=5, sum=4  
12. sum < k → end=7, sum=9  
13. sum > k → start=6, sum=5 → 기록([6,6])  
14. sum == k → start=7, sum=0
    

→ 기록된 후보:

• [0,3] (길이 4)
• [3,4] (길이 2)
• [6,6] (길이 1)

최종 선택: [6,6]

시간복잡도와 효율성 분석

• start와 end는 오른쪽으로만 움직입니다.
• 각각 최대 N번만 움직입니다.
• 따라서 전체 반복 횟수는 최대 2N
• 시간 복잡도 O(N)으로 매우 빠르고 효율적입니다.

이 구조는 “모든 원소가 양수”일 때만 가능한 전략이며, 이 문제는 그 조건을 명확히 제공합니다.

---

투포인터 시각화 — sequence = [1, 1, 1, 2, 3, 4, 5], k = 5

초기 상태

start
↓
1, 1, 1, 2, 3, 4, 5
↑
end
sumarr = 0
    

아직 아무것도 선택하지 않은 상태입니다. sum이 부족하므로 오른쪽(end)을 확장해야 합니다.

오른쪽 확장 (end += 1)

start
↓
1, 1, 1, 2, 3, 4, 5
   ↑
end
sumarr = 1
    

sumarr는 1입니다. 아직 k = 5보다 작습니다. 더 확장합니다.

또 확장

start
↓
1, 1, 1, 2, 3, 4, 5
      ↑
end
sumarr = 2
    

계속 부족합니다. 다시 확장합니다.

계속 확장

start
↓
1, 1, 1, 2, 3, 4, 5
         ↑
end
sumarr = 3
    

아직 5보다 작습니다. 한 번 더 오른쪽 확장합니다.

확장 후 sumarr == k

start
↓
1, 1, 1, 2, 3, 4, 5
            ↑
end
sumarr = 5 ✅
    

드디어 합이 k랑 같습니다. 구간: [0, 3] → [1, 1, 1, 2] 후보로 저장합니다.

이제 왼쪽을 줄여봅니다. (start += 1) → 같은 합을 만들면서 더 짧은 구간이 있는지 확인하기 위함입니다.

왼쪽 줄이기

   start
   ↓
1, 1, 1, 2, 3, 4, 5
            ↑
end
sumarr = 4
    

sequence[0]을 빼서 sumarr = 4 다시 부족해졌으므로 오른쪽을 확장해야 합니다.

오른쪽 확장

   start
   ↓
1, 1, 1, 2, 3, 4, 5
               ↑
end
sumarr = 7
    

이제 3을 더했더니 sumarr = 7 → 넘쳤습니다. 왼쪽을 줄입니다.

왼쪽 줄이기

      start
      ↓
1, 1, 1, 2, 3, 4, 5
               ↑
end
sumarr = 6
    

여전히 넘칩니다. 한 번 더 줄입니다.

또 줄이기 → sum == k

         start
         ↓
1, 1, 1, 2, 3, 4, 5
               ↑
end
sumarr = 5 ✅
    

[3, 4] → [2, 3] 후보 저장합니다. 길이는 2로 더 짧음. 이전 것([0,3], 길이 4)는 버림. 계속 왼쪽 줄이기 진행합니다.

또 줄이기

            start
            ↓
1, 1, 1, 2, 3, 4, 5
               ↑
end
sumarr = 3
    

부족합니다. 다시 확장합니다.

확장

            start
            ↓
1, 1, 1, 2, 3, 4, 5
                  ↑
end
sumarr = 7
    

넘칩니다. 줄입니다.

줄이기

               start
               ↓
1, 1, 1, 2, 3, 4, 5
                  ↑
end
sumarr = 4
    

아직 부족합니다. 그러나 더 이상 확장 불가. end가 배열 끝 도달.

마지막 확장 → sum == k

                  start
                  ↓
1, 1, 1, 2, 3, 4, 5
                  ↑
end
sumarr = 5 ✅
    

[6,6] → [5] 후보 저장. 길이 = 1 → 최단. 최종 정답이 됨.

최종 정답

[6, 6] → 합이 5인 부분 수열 중에서 가장 짧고, 가장 앞에 있는 구간

이 흐름을 기억하는 공식 리듬

sumarr 상태	행동	이유
sumarr < k	end += 1	부족하니 오른쪽에서 숫자 더 담기
sumarr > k	start += 1	넘치니 왼쪽에서 숫자 빼기
sumarr == k	후보 저장, start += 1	현재 정답 후보, 더 짧은 것 찾기 위해 왼쪽 줄이기

---

전체 코드

def solution(sequence, k):
    start = 0
    end = 0
    sumarr = sequence[0]
    min_arr = 20000000000
    answer = [0, 0]
    N = len(sequence)
    while start <= end and end < N:
        if sumarr == k:
            if (end - start) < min_arr:
                min_arr = (end - start)
                answer = [start, end]
            end += 1
            if end < N:
                sumarr += sequence[end]
        elif sumarr < k:
            end += 1
            if end < N:
                sumarr += sequence[end]
        else:
            sumarr -= sequence[start]
            start += 1
    return answer
    

정리 및 마무리

이 문제는 수학적으로나 알고리즘적으로 복잡한 문제는 아니지만, “조건을 놓치지 않고 가장 효율적인 방법으로 푸는 것”이 핵심입니다.

• 양의 정수만 있는 수열
• 정렬 여부는 크게 중요하지 않음
• 포인터를 양쪽에서 한 방향으로만 이동하며
• 합을 관리하는 슬라이딩 윈도우 방식이 정답

문제의 조건들을 하나하나 따지며 로직에 녹여내면, 자연스럽게 이 문제는 효율적으로 해결됩니다.