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

문제

문제 설명

• 비내림차순의 정렬이 주어질 때 일정 합 k를 만족하는 연속된 부분 수열을 찾아 시작 인덱스와 끝 인덱스를 반환하는 문제
• 부분 수열의 길이가 짧을수록, 시작 인덱스의 크기가 작을 수록 우선순위가 올라간다

풀이

• 부분 수열의 합이 k를 만족하지 못하는 경우 원소를 추가
• 부분 수열의 합이 k보다 크거나 같은 경우 원소 제거
  • 합이 k인 부분 수열이면 값을 기록

def solution(sequence, k):
    l = len(sequence)
    start = 0
    end = 0
    sum_v = sequence[0]
    max_length = l + 1
    result = []
    if sum_v==k:
        max_length=1
        result = [0, 0]
    while start<l and end<l:
        if sum_v<k:
            end += 1
            if end>=l:
                break
            sum_v += sequence[end]
        elif sum_v>=k:
            if sum_v==k and (end - start + 1<max_length):
                max_length = end - start + 1
                result = [start, end]
            start += 1
            if start>=l or start>end:
                break
            sum_v -= sequence[start-1]
    if not result:
        result = [start, end]
    return result