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

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

프로그래머스

 

풀이 방법

• 비내림차순으로 정렬된 수열이 있을 때, 연속된 부분 수열의 합이 k가 되는 수열 중 가장 길이가 짧고 시작 인덱스가 작은 부분 수열의 index를 찾는 문제.
• 주어진 수열을 순회하며 합이 k가 되는 부분수열을 찾고자 함.
• 하지만, 단순히 k가 되는 index를 찾았을 때 그 다음 index부터 찾고자 하면 k=5 이고 [1,1,1,2,3,4] 가 있을 때 [1,1,1,2]를 찾은 이후 [2,3]을 찾지 못하는 경우 발생.
• 따라서, while 문을 통해 제일 먼저 포함했던 원소를 제거해가며 값이 갱신되도록 해주었음. 
• ex) [1,1,1,2]가 있을 때, 앞에 들어온 [1,1,1]을 3이 대체하여 [2,3]이 되는 방식 . 또한, [1,1,1,2,2,4] 가 있을 경우, 앞선 '1' 2개를 '2' 1개가 대체할 수 있음.

 

 

풀이 코드

from collections import deque


def solution(sequence, k):
    answer = []
    length = len(sequence) - 1
    idxs = deque()
    kval = k

    for idx, i in enumerate(sequence):
        kval -= i
        idxs.append(idx)

        if kval == 0:
            answer.append([idxs[0], idxs[-1]])

        while idxs and idx < length and kval < sequence[idx + 1]:
            kval += sequence[idxs.popleft()]

    return sorted(answer, key=lambda x: x[1] - x[0])[0]