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

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

프로그래머스

비내림차순으로 정렬된 정수 수열과 부분 수열의 합(k)이 주어졌을 때, 부분 수열의 시작 인덱스와 마지막 인덱스를 반환

• 부분 수열은 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함해야 한다.
• 부분 수열의 합은 k
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾고, 길이가 짧은 수열이 여러 개인 경우, 시작 인덱스가 작은 부분 수열을 반환

Test case1.

sequence = [1, 2, 3, 4, 5] k = 7 이면, 부분 수열은 [3, 4] 

 

Solution.

이중 포인터를 이용한 누적합으로 풀기

1. 부분 수열의 인덱스는 left와 right로 설정 (부분 수열의 길이는 right-1-left)
2. total += sequence[right], total 값이 k와 같으면 answer에 left, right-1을 저장
3. total < k이면, right += 1
4. total > k이면, left 인덱스의 요소를 빼기

def solution(sequence, k):
    answer = [0,0]
    total, right = 0, 0
    n = len(sequence)
    interval = n    #부분 수열의 길이
    
    for left in range(n):
        while total < k and right < n:
            total += sequence[right]
            right += 1
            
        if total == k and right-1-left < interval:  # 부분수열 합이 total과 같고, 그 길이가 기존 수열보다 짧으면
            answer[0], answer[-1] = left, right-1
            interval = right-1-left
        total -= sequence[left]
        
    return answer