[코딩테스트] 프로그래머스 연속된 부분 수열의 합 파이썬(Python)

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

프로그래머스

def solution(sequence, k):
    prefix_sum = [0]
    sum_value = 0
    s = 0
    e = s+1
    result = [0, len(sequence)]
    for i in range(len(sequence)):
        sum_value += sequence[i]
        prefix_sum.append(sum_value)
        
    while s < e and e < len(prefix_sum):
        if prefix_sum[e] - prefix_sum[s] == k:
            if (e-1) - s < (result[1] - result[0]):
                result = [s, e-1]            
            e += 1
        elif prefix_sum[e] - prefix_sum[s] < k:
            e += 1
        else:
            s += 1
    return result

이 문제는 이전에 풀었던 문제와 유사합니다.

[코딩테스트] 백준 수열(2559) 파이썬(Python)

완전 탐색으로 푸는 것이 아니라 누적합을 구하여 문제를 해결했습니다.

 

먼저 prefix_sum 리스트에 sequence 리스트의 원소들을 누적합하여 구합니다.

 

prefix_sum의 첫번째 원소는 0입니다.

prefix_sum[1] : sum(sequence[:1])

prefix_sum[2] : sum(sequence[:2])

prefix_sum[3] : sum(sequence[:3]) 입니다.

 

while문으로 k와 동일한 부분수열의 합을 찾게됩니다.

이때 prefix_sum의 인덱스를 s, e 변수로 찾게 됩니다.

• s는 0부터 시작하고 e는 s+1부터 시작합니다.

while문의 종료조건은 s 가 e보다 커지거나 e가 prefix_sum의 범위를 벗어나면 종료합니다.

먼저 부분수열의 합이 k와 동일하다면 부분수열의 길이가 기존의 길이(result)보다 짧은지 확인하고 짧다면 result를 갱신합니다.

• 0부터 시작하기 때문에 항상 result에 저장되어있는 인덱스가 앞쪽에 나오는 수열입니다.

그리고 e 인덱스를 증가시킵니다.

만약 k보다 작다면 e 인덱스를 증가시키고 k보다 크다면 s 를 증가시킵니다.

 

여기서 2중 반복문으로 모든 인덱스를 탐색하면 시간초과가 나오기 때문에 s,e 인덱스를 만들어 투포인터로 진행하였습니다.

 

반복문이 종료되었다면 result를 반환합니다.