[Python 문제 풀이] 프로그래머스 '연속된 부분 수열의 합'

Programmers Lv.2 연속된 부분 수열의 합 / 파이썬

접근

두 개의 포인터를 놓고 부분 수열의 합을 반복해서 비교하며 위치를 옮기거나 확장한다.

 

가장 짧은 길이의 부분 수열을 찾기 위해, 더 큰 수가 위치한 뒤쪽 인덱스부터 탐색한다.

 

sequence의 길이가 길기 때문에 sum()함수를 반복해서 사용하면 시간초과가 발생할 수 있으므로 부분합 변수를 만들어 갱신하도록 한다.

 

의사코드

1. i와 j를 마지막 인덱스 번호로 초기화
2. sub_total을 마지막 원소의 값으로 초기화
3. sub_total이 k와 같아질 때까지 i, j 조정하면서 sub_total을 갱신
4. sub_total이 k와 같을 때 더 앞쪽에 있는 동일한 부분 수열을 가리키도록 i와 j를 감소

코드

def solution(sequence, k):
    i = j = len(sequence) - 1
    sub_total = sequence[-1]
    while True:
        if sub_total > k :
                i -= 1
                j -= 1
                sub_total += sequence[i]
                sub_total -= sequence[j + 1]
        elif sub_total < k:
            i -= 1
            sub_total += sequence[i]
        elif i != 0 :
            while sequence[i-1] != sequence[j] :
                i -= 1
                j -= 1
            break
    return [i,j]