[programmers] Lv2 연속된 부분 수열의 합 - Python

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

프로그래머스

 

 

 

<문제 풀이>

- 투 포인터 알고리즘을 이용하여 특정한 합을 가지는 부분 연속 수열을 찾는 문제이다.

- 알고리즘에 대한 자세한 설명은 나동빈 님의 이것이 코딩 테스트다 관련 유튜브를 참고하면 좋을 것이다.

https://www.youtube.com/watch?v=ttLRltNDiCo&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=39

 

 

 

<Code>

def solution(sequence, k):
    answer = [1111111, 9999999]
    n = len(sequence)

    interval_sum = 0    # 누적 합
    end = 0    # 마지막 idx

    for i in range(n):
        # 누적 합이 k 이상이 되거나 마지막 idx가 입력된 list의 길이를 넘지 않는 선에서 반복문 실행
        while interval_sum < k and end < n:
            interval_sum += sequence[end]
            end += 1

        if interval_sum == k:    # 누적 합이 k인 경우
            if answer[1] - answer[0] > end - 1 - i:    # 시작, 마지막 idx 차가 작은 경우 갱신
                answer = [i, end-1]
            elif (answer[1] - answer[0] == end - 1 - i) and (answer[0] > i):    # 길이가 같다면 시작 idx가 작은 경우 갱신
                answer = [i, end-1]

        interval_sum -= sequence[i]    # 현재 idx에 해당하는 값을 누적 합에서 제거 후 다음 idx 진행

    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.