연속된 부분 수열의 합 - Python, 부분합, 슬라이딩 윈도우

 

 

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

프로그래머스

 

코드 & 풀이

 

def solution(sequence, k):
    answer = []
    L, R, total, minCnt = 0, 0, 0, len(sequence)
        
    while R < len(sequence):
        total += sequence[R]
        
        while total > k and L <= R:
            total -= sequence[L]
            L += 1
        
        if total == k and minCnt > R - L:
            minCnt = R - L
            answer = [L, R]
        
        R += 1
    return answer

 

매번 합을 구하면 비효율적이겠죠

 

그렇기 때문에  누적합, 슬라이드를 적용했습니다.

 

반복문에 들어가면

 

일단 R 위치의 값을 추가합니다.

 

그 값이 K보다 크고 L이 R보다 같거나 작은 경우는

 

L값을 빼면서 L을 앞으로 당겨줍니다.

 

그 다음은 그렇게 구한 total이 K와 같으면서

 

인덱스의 길이가 기존보다 작으면

 

그 값을 저장해줍니다.

 

 

 

 

 

다음에 또 봐요