[프로그래머스] 178870. 연속된 부분 수열의 합 | 투포인터 | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

비내림차순으로 정렬된 수열 sequence과 정수k가 주어진다.

합이 k가 되는 부분수열의 시작 인덱스와 끝 인덱스를 구하라

---

문제 조건

합이 k인 부분수열이 여러개 존재할 경우 길이가 가장 짧은것, 시작 인덱스가 작은 수열을 구한다.

5 <= len(sequence) <= 100,000, 5 <= k <= 100,000,000

---

시행착오

투포인터로 접근해야한다는 것은 알았다. 근데 투포인터를 다루는 방법이 미숙했다. 

다른분의 풀이를 보고 나의 코드의 문제점을 알게되었다.

---

접근방법

1. 만약 sequence의 i번째에 k가 존재한다면 무조건 [i, i]가 정답이다.

2. 부분수열의 합을 구하기 위해 투포인터를 사용한다.

---

소스코드

def solution(sequence, k):
    answer = [0, 1000001]
    start, end, sum_value = 0, 0, 0

    for i in range(len(sequence)):
        if sequence[i] == k:
            return [i, i]

    while start < len(sequence):

        while end < len(sequence) and sum_value < k:
            sum_value += sequence[end]
            end += 1

        if sum_value == k:
            if answer[1] - answer[0] > end - 1 - start:
                answer = [start, end - 1]

        sum_value -= sequence[start]
        start += 1


    return answer