[Python][투포인터] 연속된 부분수열의 합 (투포인터)

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

프로그래머스

프로그래머스 LV2 문제

 

 

 

정렬된 배열에서 부분 배열이 제시한 K와 같을 때 해당 인덱스를 반환. 단, 최소 개수의 부분 배열이여야 함.

 

def solution(sequence, k):
    answer = []
    left = 0 ; right = 0 ; index_num = len(sequeㄴㄴnce) # 최소 배열 체크용
    cnt = sequence[left]
    # sequence 는 정렬된 배열
    while 1 :
        #print ([left, right])
        if cnt == k :
            # 최소 배열인지 체크
            if index_num > right - left :
                index_num = right - left
                answer = [left, right]
            right += 1
            if right == len(sequence) : break
            cnt += sequence[right]
        elif cnt > k :
            cnt -= sequence[left]
            left += 1

        elif cnt < k :
            right += 1
            if right == len(sequence) : break
            cnt += sequence[right]

    return answer

 

아래 표처럼, 부분 배열의 합이 입력된 K보다 크거나 같을 경우에는 R ++

K보다 작을 때는 L--

이때 부분 배열의 합을 갱신해줘야 하기에,

L-- 이전에 합에서 [Left] 값을 빼주고, R++ 한 후에 합에서 [Right] 값을 더해주면서 전진하면됨

참고 : https://velog.io/@sugyeonghh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%97%B0%EC%86%8D%EB%90%9C-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4%EC%9D%98-%ED%95%A9Python