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

문제 링크

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

프로그래머스

소스 코드

def solution(sequence, k):
    l = len(sequence)
    result = []
    tmp = sequence[0] # 초깃값
    right = 0
    
    for left in range(l):
        while (right < l-1) and (tmp < k): # 범위 만족 & 부분합이 k보다 작을 때
            right += 1
            tmp += sequence[right] # 오른쪽 값을 추가
            
        if tmp == k:
            if not result: # 비어있는 경우
                result = [left,right]
            elif right-left < result[1]-result[0]: # 간격이 더 좁은 경우 업데이트
                result = [left,right]
        
        tmp -= sequence[left] # 왼쪽 한 칸 덜어내기
    
    return result

해설

• 투 포인터

left, right 두 개의 변수를 포인터로 사용하여 선형 탐색시간으로 문제를 풀이하는 알고리즘입니다.

GPT에게 위 풀이에 대해 간단히 설명하고 시간 복잡도를 분석하라고 했는데 굉장히 깔끔하게 답변을 해주네요.. ㄷㄷ

 

예.. 뭐 굳이 더 설명할 필요가 없을 정도로 깔끔하고 완벽한 해설입니다..!

 

조금만 덧붙이자면 제한 조건을 빠르게 파악할 필요가 있던 문제입니다.

sequence의 길이가 굉장히 길기 때문에 이를 선형탐색하지 않으면 안 되는 문제입니다.

예를 들어 이중 for문으로 문제를 풀이하게 된다면, 최악의 경우 "백만 x 백만"의 연산이 요구되기 때문에 절대로 풀이할 수 없습니다.

 

물론 위에 구현된 투 포인터 알고리즘의 경우 for문 안에 while문이 존재하긴 하지만, 

left 변수가 선형증가하게 되어있고, 중복되는 경우를 다루지 않기 때문에 효율적입니다.

right 변수 역시 감소하는 일은 없고 계속해서 선형증가하므로 중복되는 케이스 없이 효율적으로 탐색을 수행할 수 있게 됩니다.