[programmers/py] 연속된 부분 수열의 합

연속된 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=javascript

문제 설명

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

풀이

투 포인터 문제

• for문을 두 번 사용하면 시간 초과가 나옴

1.sequence의 합을 미리 계산한 arr list를 생성
2. list의 차이를 통해 값을 구한다.

def solution(sequence, k):
    answer = []
    arr = [sequence[0]]
    
    l_s = len(sequence)
    
    for i in range(1, l_s):
        arr.append(sequence[i] + arr[-1])
    
    start = 0
    end = 0
    answer = None
    answer_idx = None
    cnt = 0
    
    while start <= end and l_s > end :
        val = arr[end] - arr[start] + sequence[start]
        
        if val == k:
            if answer is None:
                answer = [start, end]
            else :
                if (answer[1] - answer[0]) > (end - start):
                    answer = [start, end]
        
        if start == end:
            end += 1
        elif val > k :
            start += 1
        else:
            end += 1
    
    return answer