[프로그래머스] 연속된 부분 수열의 합 (Lv.2) - 파이썬 풀이

---

풀이

  투포인터 방법을 이용한다. left 포인터를 고정시키고 left 포인터 뒤부터 차례대로 훑어가면서 부분합을 누적시키고, 부분합이 k에 도달하였을 때 left와 right 인덱스를 정답 후보군 배열(result)에 추가해준다.

  그 뒤 result 배열을 right - left 순으로 정렬해준 뒤, 길이가 가장 짧은 부분 수열을 리턴한다.

 

# 프로그래머스 연속된 부분 수열의 합 LV2 https://school.programmers.co.kr/learn/courses/30/lessons/178870
def solution(sequence, k):
    result = []
    right = 0
    summation = 0
    for left in range(len(sequence)):
        while right < len(sequence) and summation < k:
            summation += sequence[right] 
            right += 1
            
        if summation == k:
            result.append((left, right-1))
                
        # 다음 구간을 더 탐색하기 위해 앞쪽 값을 버린다.
        summation -= sequence[left]

        # left~right의 길이가 가장 짧은 순으로 정렬한다.
        result.sort(key=lambda x: x[1]-x[0])

    return result[0]

 

문제 출처

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