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

문제

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

프로그래머스

풀이

$5 \leq \text{len(sequence)} \leq 1,000,000$ 의 제한사항이 있기 때문에, 시간초과에 유의해서 코드를 작성해야한다.

def solution(sequence, k):
    l,r = 0,0
    s = 0
    answers = []
    for i in range(len(sequence)):
        s+=sequence[i]
        if s==k:
            answers.append([l,r])
            s-=sequence[l]
            l+=1
        elif s>k:
            while s>k:
                s-=sequence[l]
                l+=1
                if s==k:
                    answers.append([l,r])
        r+=1
        
    return sorted(answers,key=lambda x:(x[1]-x[0],x[0]))[0]

sequence를 순회하면서 s(합)에 현재 값을 추가해 원소의 합을 k와 비교한다.

• k와 같은 경우
  • answers에 추가하고 더 있을지도 모르는 정답을 계산하기 위해 left index를 하나 증가시키고 그 전의 index에 해당하는 원소값을 s에서 빼준다
• k보다 큰 경우
  • 이미 해당 left index에서는 정답이 나올 수 없기 때문에 s가 k보다 작아질때 까지 left index를 증가시키고 해당 원소값을 s에서 빼준다
  • 그 후에 k와 비교해 같은 경우에는 answers에 추가한다
• 순회가 끝난 후에 우선순위에 따라 answers를 정렬하고 첫번째 원소를 return