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

문제

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

프로그래머스

위 문제는 비내림차순으로 정렬된 수열이 주어질 때, 부분 수열의 합이 k인 구간을 찾고, 구간이 여러개 존재하게 되면 그 구간의 길이가 짧은 것을 구해줘야 하는 문제 입니다. sequence의 길이가 1,000,000이기 때문에 O(N^2)의 시간 복잡도로 이루어진다면 시간 초과가 발생하게 됩니다. 따라서 구간합과 투포인터를 활용하여 부분 수열의 합이 k인 구간을 찾아주고, 이 구간들의 길이를 계속적으로 비교해주며 문제를 해결할 수 있습니다.

Python

def solution(sequence, k):
    answer = []
    
    #구간합 배열 만들기
    prefix = [0]
    sum = 0
    for i in sequence:
        sum += i
        prefix.append(sum)
        
    result = [0, len(prefix)]
    s,e = 0,1
    
    while s < e and e < len(prefix):
        if prefix[e] - prefix[s] == k:
            if e-1 - s < result[1] - result[0]:
                result = [s, e-1]
            e+=1
        elif prefix[e] - prefix[s] < k:
            e+=1
        else:
            s+=1
    return result